2
$\begingroup$

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"]

A planar graph

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ – Szabolcs Mar 12 '20 at 14:11
2
$\begingroup$

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]

enter image description here

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

enter image description here 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]

enter image description here

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.