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.