# Planar graph layout

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.

• AbsoluteOptions[graph, VertexCoordinates] Sep 20, 2014 at 17:53
• Or, for a specifically named vertex v, PropertyValue[{g, v}, VertexCoordinates] or PropertyValue[g, VertexCoordinates] for all coordinates. Sep 20, 2014 at 18:41
• @BobHanlon So, nothing leaps to mind for the faces? Sep 20, 2014 at 20:38
• check this : mathematica.stackexchange.com/questions/18514/… Sep 21, 2014 at 3:24
• @Mr.Wizard Sort of. My question is "where does Mathematica store this information" (since you need to generate to do the planar layout), and what halmir's comment says is that people asked the question of how to find the faces before, and he came up with his (nice) answer. However, his question does not answer (except by implication) whether this information is actually just stashed somewhere, where it could be extracted with a one line request - this is the subtext of my question to him - it is quite possible that his way is quite slow for a large graph (both in complexity and in constants... Sep 21, 2014 at 10:25

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.

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