How to get a plane drawing according to the rotation system given

Question

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.

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

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]

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]

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.

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]

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]

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

Answer 1

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]

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

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