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.

  • $\begingroup$ I'm posting a similar question requiring a simple dual graph here $\endgroup$ – becko Jun 10 '12 at 0:18

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.

great rhombicosidodecahedron

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.

  • 1
    $\begingroup$ Actually, the dual can be "constructed" from the gem representation in zero time, by a simple typecast. The same data structure represents both the original map and its dual. $\endgroup$ – Jeffε Jun 6 '12 at 1:59
  • 1
    $\begingroup$ Also, to "choose a circular ordering for the edges incident to each vertex", I recommend using the ordering in the adjacency list data structure you're using to represent the graph anyway. $\endgroup$ – Jeffε Jun 6 '12 at 2:03
  • $\begingroup$ @JɛffE and David Eppstein. Thanks for the answer and helpful comments. I wanted to finish programming this GEM approach to my problem before I posted again here. I have run into an issue, though. The dual graph $G'$ I am obtaining is almost always a multigraph. How can I avoid dual multigraphs? $\endgroup$ – becko Jun 9 '12 at 18:12
  • $\begingroup$ +1 This post clearly answers the question as I stated it. I don't know if I should mark this as the answer right now and start a new post with the new issue, or modify this post, since the issue is clearly in context here. $\endgroup$ – becko Jun 9 '12 at 18:16
  • 1
    $\begingroup$ You know how many vertices, edges, and faces you have, so you can compute the genus from the Euler characteristic (with a little care for whether the surface is orientable or not). $\endgroup$ – David Eppstein Jun 10 '12 at 7:29

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.