To kick things off, I tried randomly moving the new interior into the chosen triangle (new exterior). If somebody came up with a function that could detect edge crossings, then this could run many times until a good configuration appeared - I doubt it wouldn't scale well for larger graphs, though it's a start:
(* Move the chosen points into the new exterior randomly *) exteriorChange[G_, ext_] := Module[{coords = GraphEmbedding[G], tri, newpoints}, tri = Polygon[coords[[ext]]]; newpoints = If[MemberQ[ext, #], coords[[#]], RandomPoint[tri]] & /@ VertexList[G]; Return[PlanarGraph[EdgeList[G], VertexCoordinates -> newpoints, VertexLabels -> "Name"]]] SeedRandom[53]; G = PlanarGraph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 2 <-> 3, 3 <-> 4, 2 <-> 5, 5 <-> 6, 6 <-> 3}, VertexLabels -> All] Show[ Graphics[{EdgeForm[None], FaceForm[LightGray]}], exteriorChange[G, {1, 2, 3}] ] 