4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ AbsoluteOptions[graph, VertexCoordinates] $\endgroup$ – Bob Hanlon Sep 20 '14 at 17:53
  • $\begingroup$ Or, for a specifically named vertex v, PropertyValue[{g, v}, VertexCoordinates] or PropertyValue[g, VertexCoordinates] for all coordinates. $\endgroup$ – Sjoerd C. de Vries Sep 20 '14 at 18:41
  • $\begingroup$ @BobHanlon So, nothing leaps to mind for the faces? $\endgroup$ – Igor Rivin Sep 20 '14 at 20:38
  • 2
    $\begingroup$ check this : mathematica.stackexchange.com/questions/18514/… $\endgroup$ – halmir Sep 21 '14 at 3:24
  • 1
    $\begingroup$ @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... $\endgroup$ – Igor Rivin Sep 21 '14 at 10:25
6
$\begingroup$

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

enter image description here

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

IGLayoutPlanar[g]

enter image description here

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]

enter image description here

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

enter image description here

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

enter image description here

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]

enter image description here

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} &]
 ]

enter image description here

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]

enter image description here

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]

enter image description here

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.

$\endgroup$
3
$\begingroup$

Several ways to get the vertex coordinates:

g = RandomGraph[BarabasiAlbertGraphDistribution[15, 2]]

enter image description here

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

enter image description here

$\endgroup$

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.