Planar graph layout

Question

Mathematica supplies planar graph layout, which draws a nice picture of a planar graph, but is there any way to get one's hands on the layout? For example, to find its faces (complementary regions)? Also, in principle, the coordinates of the vertices would be nice.

Answer 1

If you have a layout, you can get the vertex coordinates using GraphEmbedding.

IGraph/M provides a lot of planar-graph related functionality that is not available with builtin functions. I'll show a few examples:

g = GraphData["TutteGraph"]

In addition to the built-in planar layout, IGraph/M provides IGLayoutPlanar, which implements Schynder's algorithm.

IGLayoutPlanar[g]

These types of drawings are not terribly exciting or readable though. The Tutte layout is usually nicer. It is available built-in, but the IGraph/M version has extra features.

This is what it gives by default:

IGLayoutTutte[g]

This is the same result that we'd get with GraphLayout -> "TutteEmbedding". It is not nice, however, because it does not reflect the symmetries of the graph.

Luckily, IGLayoutTutte allows specifying the outer face:

tg = IGLayoutTutte[g, "OuterFace" -> {2, 3, 4, 5, 6, 7, 8, 9, 10}]

Now that's much nicer! It is also perfectly symmetric, unlike the layout that comes with GraphData, which looks to be hand-drawn for this graph.

It also supports weights. There's a nice trick where we lay out the graph once, then use the edge lengths as weights to obtain a stretched layout.

IGLayoutTutte[
 IGEdgeMap[Apply[EuclideanDistance], 
  EdgeWeight -> IGEdgeVertexProp[VertexCoordinates], tg], 
 "OuterFace" -> {2, 3, 4, 5, 6, 7, 8, 9, 10}]

There's a Manipulate in the documentation (IGDocumentation[]) that shows how to control the amount of the stretching.

How do we get the faces?

IGFaces[g]
(* {{1, 11, 14, 22, 8, 2, 20, 26, 27, 12}, {1, 12, 29, 28, 4, 5,
   34, 33, 32, 13}, {1, 13, 31, 30, 7, 10, 25, 19, 15, 11}, {2, 3, 42,
   41, 20}, {2, 8, 9, 10, 7, 6, 5, 4, 3}, {3, 4, 28, 40, 42}, {5, 6, 
  46, 44, 34}, {6, 7, 30, 45, 46}, {8, 22, 21, 23, 9}, {9, 23, 24, 25,
   10}, {11, 15, 16, 14}, {12, 27, 35, 29}, {13, 32, 36, 31}, {14, 16,
   17, 21, 22}, {15, 19, 18, 17, 16}, {17, 18, 24, 23, 21}, {18, 19, 
  25, 24}, {20, 41, 39, 26}, {26, 39, 37, 35, 27}, {28, 29, 35, 37, 
  40}, {30, 31, 36, 38, 45}, {32, 33, 43, 38, 36}, {33, 34, 44, 
  43}, {37, 39, 41, 42, 40}, {38, 43, 44, 46, 45}} *)

Visualize them:

cycle = PathGraph[Append[#, First[#]]] &;

HighlightGraph[tg, cycle[#]] & /@ IGFaces[g]

After removing the outer face (which was explicitly set when creating the Tutte layout stored in tg), we can make a MeshRegion:

MeshRegion[
 GraphEmbedding[tg],
 Polygon@Select[IGFaces[tg], 
   Sort[#] =!= Sort@{2, 3, 4, 5, 6, 7, 8, 9, 10} &]
 ]

We can also get a combinatorial embedding:

emb = IGPlanarEmbedding[g]
(* <|1 -> {11, 12, 13}, 2 -> {3, 20, 8}, 3 -> {2, 4, 42}, 
 4 -> {3, 5, 28}, 5 -> {4, 6, 34}, 6 -> {5, 7, 46}, 7 -> {6, 10, 30}, 
 8 -> {2, 22, 9}, 9 -> {8, 23, 10}, 10 -> {9, 25, 7}, 
 11 -> {1, 15, 14}, 12 -> {1, 27, 29}, 13 -> {1, 32, 31}, 
 14 -> {11, 16, 22}, 15 -> {11, 19, 16}, 16 -> {15, 17, 14}, 
 17 -> {16, 18, 21}, 18 -> {17, 19, 24}, 19 -> {18, 15, 25}, 
 20 -> {2, 41, 26}, 21 -> {17, 23, 22}, 22 -> {21, 8, 14}, 
 23 -> {21, 24, 9}, 24 -> {23, 18, 25}, 25 -> {24, 19, 10}, 
 26 -> {20, 39, 27}, 27 -> {26, 35, 12}, 28 -> {4, 29, 40}, 
 29 -> {28, 12, 35}, 30 -> {7, 31, 45}, 31 -> {30, 13, 36}, 
 32 -> {13, 33, 36}, 33 -> {32, 34, 43}, 34 -> {33, 5, 44}, 
 35 -> {29, 27, 37}, 36 -> {32, 38, 31}, 37 -> {35, 39, 40}, 
 38 -> {36, 43, 45}, 39 -> {37, 26, 41}, 40 -> {37, 42, 28}, 
 41 -> {39, 20, 42}, 42 -> {41, 3, 40}, 43 -> {38, 33, 44}, 
 44 -> {43, 34, 46}, 45 -> {38, 46, 30}, 46 -> {45, 44, 6}|> *)

These are counter-clockwise orderings of adjacent vertices around each vertex.

We could have gotten the faces just from the embedding:

IGFaces[emb]

We could also have gotten the combinatorial embedding from already known vertex coordinates, such as the ones contained in GraphData:

IGCoordinatesToEmbedding[g]

We can get the dual graph:

IGDualGraph[g]

Note that this contains the outer face too. If we don't want that, we could also obtain a dual graph from the mesh we created earlier, even including coordinates.

IGMeshCellAdjacencyGraph[mesh, 2, VertexCoordinates -> Automatic]

Just like IGFaces, IGDualGraph works both on graphs and combinatorial embeddings.

There are several other useful functions too, such as IGMaximalPlanarQ, IGOuterPlanarQ. We can compute planar coordinates based on a given planar combinatorial embedding with IGEmbeddingToCoordinates. We can find the IGKuratowskiEdges if the graph is not planar. We can convert a combinatorial embedding back to a graph using IGAdjacencyGraph[emb]. Check the documentation for more examples. It's a practical little toolkit.

One limitation I should mention is that multi-graphs are unfortunately not supported at this moment for this particular functionality area. Sadly, Mathematica's Graph itself is not very helpful with this, as it does not allow distinguishing between parallel edges, which would be necessary just to store a combinatorial embedding properly. It should really be counter-clockwise ordering of incident edges, not adjacent vertices.

Answer 2

Several ways to get the vertex coordinates:

g = RandomGraph[BarabasiAlbertGraphDistribution[15, 2]]

v1 = GraphEmbedding[g]
(* {{1.51112,1.79164},{1.96659,2.33322},{1.69272,1.22345},{1.26659,0. 698685},
   {0.707776,0.695621},{2.39199,0.702118},{2.798,1.67443},{1.00596,2. 14422},
   {0.317993,2.08198},{0.891194,1.40115},{2.70447,2.43294},{1.66747,0. },
   {0.,1.08197},{0.646005,2.80554},{2.38412,1.371}} *)
v2 = VertexCoordinates /. AbsoluteOptions[g, VertexCoordinates];
v3 = PropertyValue[{g, #}, VertexCoordinates] & /@ VertexList[g];
v4 = Cases[Show[g], DiskBox[x_, y__] :> x, {0, Infinity}];

For version 10, use v4b instead of v4

v4b = Show[g][[1,1]];

v1 == v2 == v3 == v4
(*  True  *)

To get the vertex coordinates of a graph associated with a specific embedding, say "PlanarEmbedding":

vcplanar = GraphEmbedding[g, "PlanarEmbedding"]
(* {{0., 0.}, {6., 3.}, {8., 2.}, {2., 11.}, {2., 7.}, {12., 2.}, 
    {0., 14.}, {6., 4.}, {3., 6.}, {14., 0.}, {1., 12.}, {9., 3.}, 
    {3.,  7.}, {3., 5.}, {8., 1.}} *)

SetProperty[g, VertexCoordinates -> vcplanar]
(* or *) SetProperty[g, GraphLayout ->"PlanarEmbedding"]