4
$\begingroup$

A rotation system is an ordering of neighbours around each vertex that defines a particular embedding of the graph in the plane.

For example, below is the rotation system of a plane graph.

1: 2->3->4->6
2: 1
3: 1
4: 1->5
5: 4->6
6: 1->5

The rotation system specifies the four neighbours of vertex 1 are 2 then 3 then 4 then 6 in clockwise order. We can draw following plane graph by this rotation system. We care about the labels of the vertices of the graph that we draw.

enter image description here

Below is the same planar graph as above, but with a completely different system rotation.

enter image description here

When I run follow codes in Mathematica, I saw that it returned a planar graph that matched the rotation system above if we don't care about clockwise or counterclockwise.

  PlanarGraph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 4, 
  1 \[UndirectedEdge] 3, 4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6,
   6 \[UndirectedEdge] 1}, VertexLabels -> Automatic]

enter image description here

But if I change the order of the edges in the function PlanarGraph, the plane drawing returned may not conform to the rotation system. (The plane drawing returned is really bad.)

PlanarGraph[{1 \[UndirectedEdge] 2, 6 \[UndirectedEdge] 1, 
      1 \[UndirectedEdge] 4, 5 \[UndirectedEdge] 6, 1 \[UndirectedEdge] 3,
       4 \[UndirectedEdge] 5}, VertexLabels -> Automatic]

enter image description here

I am sure how to get the plane drawing consistent with the rotation system, instead of randomly trying to adjust the order of edges in PlanarGraph. What are the guidelines for labelling the plane graphs returned by Mathematica?


In the case of a three-connected graph, the situation appears to be improved, as demonstrated in the following illustration:

below is the rotation system of a 3-connected plane graph.

1: -> 2 -> 3 -> 6 -> 5

2: -> 4 -> 3 -> 1 -> 5

3: -> 1 -> 2 -> 4 -> 6

4: -> 2 -> 5 -> 6 -> 3

5: -> 1 -> 6 -> 4 -> 2

6: -> 1 -> 3 -> 4 -> 5

We can draw following plane graph by this rotation system.

![enter image description here

When I run follow codes in Mathematica, I saw that it returned a planar graph that matched the rotation system above.

 PlanarGraph[{1 \[UndirectedEdge] 2, 1 \[UndirectedEdge] 3, 
  1 \[UndirectedEdge] 6, 1 \[UndirectedEdge] 5, 2 \[UndirectedEdge] 3,
   2 \[UndirectedEdge] 4, 2 \[UndirectedEdge] 5, 
  4 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 6, 4 \[UndirectedEdge] 5,
   4 \[UndirectedEdge] 6, 5 \[UndirectedEdge] 6}, 
 VertexLabels -> Automatic]

enter image description here

But if I change the order of the edges of the PlanarGraph, The plane drawing always seems to conform to the rotation system, regardless of whether clockwise or counterclockwise.

 PlanarGraph[{1 \[UndirectedEdge] 6, 3 \[UndirectedEdge] 6, 
  5 \[UndirectedEdge] 6, 2 \[UndirectedEdge] 3, 4 \[UndirectedEdge] 3,
   4 \[UndirectedEdge] 5, 2 \[UndirectedEdge] 5, 
  2 \[UndirectedEdge] 1, 1 \[UndirectedEdge] 5, 2 \[UndirectedEdge] 4,
   1 \[UndirectedEdge] 3, 4 \[UndirectedEdge] 6}, 
 VertexLabels -> Automatic]

enter image description here

Note, however, that the order of vertex neighbors is the same as above if rotated counterclockwise.

$\endgroup$

1 Answer 1

2
$\begingroup$

IGEmbeddingToCoordinates from IGraph/M will do this. However, the result is not usually pretty. Try IGLayoutPlanar on a few graphs to see what you might expect. It uses Schnyder's algorithm, as implemented in the LEMON graph library.

Example:

g = IGShorthand["a-b-c-d-a-e-d"]

Get a planar drawing:

IGLayoutPlanar[g]

enter image description here

The combinatorial embedding (rotation system) that IGLayoutPlanar uses is the following:

emb = IGPlanarEmbedding[g]
(* <|"a" -> {"b", "d", "e"}, "b" -> {"a", "c"}, 
 "c" -> {"b", "d"}, "d" -> {"c", "e", "a"}, "e" -> {"d", "a"}|> *)

We can convert an embedding to coordinates using IGEmbeddingToCoordiates. Let us try a slightly different embedding of the same graph:

emb2 = <|"a" -> {"e", "d", "b"}, "b" -> {"c", "a"}, "c" -> {"d", "b"},
    "d" -> {"c", "a", "e"}, "e" -> {"d", "a"}|>;

Graph[g, VertexCoordinates -> IGEmbeddingToCoordinates[emb2]]

enter image description here

If you have a drawing of a graph, you can use IGCoordinatesToEmbedding to get an embedding for it. It may not be planar though! For example, taking the original drawing of g, which happens to be planar, we can get a third drawing from IGEmbeddingToCoordinates. It's not as pretty as the original though, even if equivalent ...

Graph[g, 
 VertexCoordinates -> 
  IGEmbeddingToCoordinates@IGCoordinatesToEmbedding[g]]

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.