# Choosing bounding cycle for plot of planar graph

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.

• I think that if you are going to be working with planar graphs and graph embeddings in Mathematica, then IGraph/M is a must-have IMO. Of course, as the author of this package, I might be a bit biased ;-) But Mathematica can't really do much with planar graphs on its own. – Szabolcs Mar 12 '20 at 14:11

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

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.

• This looks perfect for me. I'm thinking about polyhedra, so 3-vertex-connected is fine by me. Thank you! – Chris Atkinson Mar 12 '20 at 14:18