Choosing bounding cycle for plot of planar graph

Question

Is it possible to specify bounding face for drawing a planar embedding of a planar graph? For example, look at the following:

PlanarGraph[{{1, 2}, {1, 5}, {1, 6}, {1, 3}, {7, 9}, {7, 8}, 
  {2, 3}, {2, 4}, {2, 5}, {8, 9}, {3, 6}, {3, 4}, {4, 9}, {4, 8}, 
  {5, 8}, {5, 7}, {6, 7}, {6, 9}}, VertexLabels -> "Name"]

The bounding face here is the cycle {1,5,7,6}. Is it possible, for example, to instruct Mathematica to draw the embedding where the triangle {1,2,5} is the bounding face?

I've looked through the documentation and haven't found what I'm looking for.

Answer 1

Is it possible, for example, to instruct Mathematica to draw the embedding where the triangle {1,2,5} is the bounding face?

The IGraph/M package can do this, and also a lot more with planar graphs.

Mathematica implements the Tutte embedding as GraphLayout -> "TutteEmbedding", but it won't let you choose the outer face. IGLayoutTutte will.

g = Graph[{{1, 2}, {1, 5}, {1, 6}, {1, 3}, {7, 9}, {7, 8}, {2, 3}, {2,
      4}, {2, 5}, {8, 9}, {3, 6}, {3, 4}, {4, 9}, {4, 8}, {5, 8}, {5, 
     7}, {6, 7}, {6, 9}}, VertexLabels -> "Name"];

IGLayoutTutte[g]

IGLayoutTutte[g, "OuterFace" -> {1, 2, 5}]

These are the faces:

IGFaces[g]
(* {{1, 2, 3}, {1, 3, 6}, {1, 6, 7, 5}, {1, 5, 2}, {2, 5, 8, 
  4}, {2, 4, 3}, {3, 4, 9, 6}, {4, 8, 9}, {5, 7, 8}, {6, 9, 7}, {7, 9,
   8}} *)

You can choose any of them:

IGLayoutTutte[g, "OuterFace" -> #] & /@ IGFaces[g]

Note that IGLayoutTutte only works with 3-vertex-connected graphs (see Tutte embedding). Some software relax this restriction. Mathematica's built-in GraphLayout -> "TutteEmbedding" does too, but not very well: it will frequently result in overlapping edges. Maple does a better job by inserting additional edges/vertices before performing the layout. I was thinking of implementing something similar for IGraph/M, but I have not yet had the opportunity to figure out the best way to do it. Any suggestions on how to do this well are most welcome.