Finding a dual of a graph

Question

According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ handles, and below $S_n$ refers to the sphere with exactly $n$ handles), one can define a dual multigraph by treating the faces of the original graph embedding as vertices and adding an edge between two vertices for every side the corresponding faces have in common in the original graph.

Here's my problem. Given a graph $G$, I need to find another graph $G'$ such that there exists a surface $S$ and a cellular embedding of $G$ on $S$ such that $G'$ is the dual of this embedding of $G$. I know that there are many possible graphs $G'$; I just need to find one for every graph $G$.

I have several questions. My current strategy is to (1) determine the genus $n$ of $G$, (2) find an embedding of $G$ on $S_n$, and (3) find the dual of this embedding. All those steps have known algorithms (although (1) is NP-Hard). I wonder if there's a way to find a $G'$ that bypasses the computation of the genus, since that is the bottleneck of this approach, and that's my first question. My second question is: If I know that $G$ is regular, can that ease the computation of the genus? And my third question is a request for any references that can help me solve this problem.

Answer 1

Does your dual have to be of minimum genus? Because it's trivial to find a cellular embedding for any graph: just choose a circular ordering for the edges incident to each vertex, arbitrarily, and then determine the faces of the embedding as the sequences of edges consistent with the chosen orderings.

I like the GEM (graph-encoded map) representation of an embedding from the book Foundations of Topological Graph Theory by Bennington and Little. In this representation, an embedding is represented by a 3-edge-colored 3-regular graph with one vertex for every flag of the embedding (an incident triple of vertex, edge, and face) and one edge for every two flags that differ in only one of the elements of the vertex/edge/face sets that they represent. For instance, the image below from Wikipedia can be interpreted as a GEM of a regular dodecahedron, in which the red cycles represent its faces, the yellow cycles represent its edges, and the blue cycles represent its vertices; the edges may be colored according to the colors of their two incident faces.

Given a circular ordering of the edges of a graph G, its GEM can be found by making a cycle of 2d vertices for each degree-d vertex of G, two for each edge, with the pairs of vertex for each incident edge occurring in the cycle in the chosen circular order, and then for each edge e of G linking the two pairs of GEM edges for the two endpoints of e into a rectangle. If you want an oriented embedding the choice of how to link these four vertices into a rectangle should be consistent with the circular orderings, otherwise it can be arbitrary.

Then, the vertices, edges, and faces of the embedding of G are represented by cycles in the GEM that alternate between two of the three edge colors. The dual of G is represented by a GEM with the same underlying 3-regular graph but with two of its edge colors swapped. And the graph represented by a GEM can be formed by contracting all of its vertex cycles and merging pairs of parallel edges into single edges. So constructing a dual of G (as long as you don't care which dual) can easily be done in linear time.