<p>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.</p>

<p>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.</p>

<p><img src="https://i.sstatic.net/L8RH0.png" alt="great rhombicosidodecahedron"></p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-06T01:59:24.833Z
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.
Jeffε
CC BY-SA 3.0
2012-06-06T02:03:15.610Z
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.
Jeffε
CC BY-SA 3.0
2012-06-09T18:12:46.113Z
@JɛﬀE 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?
a06e
CC BY-SA 3.0
2012-06-09T18:16:42.473Z
+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.
a06e
CC BY-SA 3.0
2012-06-10T00:09:22.270Z
I think I am going to start a new question...
a06e
CC BY-SA 3.0
2012-06-10T04:12:18.690Z
@JɛﬀE and David Eppstein. Given the gem representation of some embedding, there must be a way to compute the genus of the embedding. What is it?
a06e
CC BY-SA 3.0
2012-06-10T07:29:40.180Z
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).
David Eppstein
CC BY-SA 3.0
2012-06-10T17:59:51.217Z
Thanks. Another issue I am having is that the dual graph has too few vertices (i.e., the primal graph has too few faces). I created a 4-regular (random) graph on ~2000 vertices, and the dual turns out to have ~10 vertices! I suppose this has something to do with the fact that the brute embedding I am generating (random ordering of edges incident on vertices) has too high genus.
a06e
CC BY-SA 3.0
2012-06-05T05:23:51.097Z
2012-06-05T11:43:39.283Z
2012-06-05T11:43:39.283Z
David Eppstein
<p>According to the book Topological Graph Theory by Gross and Tucker, given a <a href="http://en.wikipedia.org/wiki/Graph_embedding#Terminology">cellular embedding</a> 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. </p>

<p>Here's my <strong>problem</strong>. 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$.</p>

<p>I have several <strong>questions</strong>. 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.</p>

CC BY-SA 3.0
2012-06-10T00:18:25.003Z
I'm posting a similar question requiring a **simple** dual graph [here](http://cstheory.stackexchange.com/q/11684/5982)
a06e
<ds.algorithms><reference-request><graph-theory><cg.comp-geom><topological-graph-theory>
Finding a dual of a graph
a06e
# Finding a dual of a graph

(Asked by: username_0 on 2012-06-05)

According to the book Topological Graph Theory by Gross and Tucker, given a [cellular embedding](http://en.wikipedia.org/wiki/Graph_embedding#Terminology) 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.

**Tags:** ds.algorithms, reference-request, graph-theory, cg.comp-geom, topological-graph-theory
> **Comments:**
> **username_0**: I'm posting a similar question requiring a **simple** dual graph [here](http://cstheory.stackexchange.com/q/11684/5982)  

---

## 1 answers

### Answer by username_1 on 2012-06-05. Score: 17 | Accepted answer

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](https://i.sstatic.net/L8RH0.png)

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.

> **Comments:**
> **username_2**: 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.  
> **username_2**: 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.  
> **username_0**: @JɛﬀE 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?  
> **username_0**: +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.  
> **username_0**: I think I am going to start a new question...  
> **username_0**: @JɛﬀE and David Eppstein. Given the gem representation of some embedding, there must be a way to compute the genus of the embedding. What is it?  
> **username_1**: 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).  
> **username_0**: Thanks. Another issue I am having is that the dual graph has too few vertices (i.e., the primal graph has too few faces). I created a 4-regular (random) graph on ~2000 vertices, and the dual turns out to have ~10 vertices! I suppose this has something to do with the fact that the brute embedding I am generating (random ordering of edges incident on vertices) has too high genus.  

---

