<p>For 3-regular graphs, having a simple dual is the same thing as having a polyhedral embedding (an embedding in which each face is a simple cycle and every two faces intersect in an empty set, a vertex, or an edge). But testing for the existence of a polyhedral embedding is known to be NP-complete: see B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, <a href="http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf">http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf</a></p>

<p>I'm not sure whether polyhedral embeddability is known to remain NP-complete when restricted to 3-regular graphs — it doesn't seem to be in Mohar's paper — but it seems very likely to be true.</p>

CC BY-SA 3.0
2012-06-14T03:55:34.327Z
I delayed marking this as the answer hoping I could get additional information from other answers. Thanks!
a06e
CC BY-SA 3.0
2012-06-15T04:30:21.900Z
Do you know where I can find some more information about polyhedral embeddings? Specifically, it would be nice if I could read an explanation of an algorithm that finds a polyhedral embedding of a graph if there is one. (Perhaps you know how to do it?)
a06e
CC BY-SA 3.0
2012-06-23T03:32:05.720Z
related: http://cstheory.stackexchange.com/q/11735/5982
a06e
CC BY-SA 3.0
2012-06-10T07:41:31.010Z
2012-06-10T07:41:31.010Z
David Eppstein
<p>Given a <a href="http://en.wikipedia.org/wiki/Graph_embedding#Terminology" rel="nofollow">cellular embedding</a> of a graph on a surface (by 'surface' I mean here a sphere with some $n\geq 0$ 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 <strong>simple</strong> graph $G$, I need to find another <strong>simple</strong> 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$. Some simple graphs $G$ do not have simple duals on any surface (for example, a simple path; see JɛﬀE's comment). On the other hand, I think that for some simple graphs $G$, there can be many possible simple duals $G'$, depending on the surface and the embedding chosen.</p>

<p><strong>Question</strong>: Given a simple graph $G$, give a method that finds a simple dual graph $G'$, if it exists.</p>

<p>None of the embeddings is required to be of minimum genus. The graphs are assumed to be connected.</p>

CC BY-SA 3.0
2012-06-10T00:23:57.787Z
In a [previous question](http://cstheory.stackexchange.com/q/11648/5982) I asked for a method to obtain a dual multigraph. [This answer](http://cstheory.stackexchange.com/a/11649/5982) provides a clear exposition of such a method. Here I am asking for a method to obtain a **simple** dual graph.
a06e
CC BY-SA 3.0
2012-06-10T02:13:25.703Z
Some graphs do not have simple duals.  Consider a graph consisting of a single simple path.  This graph has a unique embedding on the sphere, whose dual is a bouquet of circles (and no cellular embedding on any other surface).
Jeffε
CC BY-SA 3.0
2012-06-10T02:17:05.073Z
@JɛﬀE Thanks. I'll try to improve the question.
a06e
CC BY-SA 3.0
2012-06-10T02:25:05.503Z
In general, if a graph has a vertex of degree one, there will be a loop in the dual graph, for all embeddings.
a06e
<ds.algorithms><reference-request><graph-theory><cg.comp-geom><topological-graph-theory>
Finding a simple dual of a simple graph in some surface
a06e
# Finding a simple dual of a simple graph in some surface

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

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), 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 **simple** graph $G$, I need to find another **simple** 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$. Some simple graphs $G$ do not have simple duals on any surface (for example, a simple path; see JɛﬀE's comment). On the other hand, I think that for some simple graphs $G$, there can be many possible simple duals $G'$, depending on the surface and the embedding chosen.

**Question**: Given a simple graph $G$, give a method that finds a simple dual graph $G'$, if it exists.

None of the embeddings is required to be of minimum genus. The graphs are assumed to be connected.

**Tags:** ds.algorithms, reference-request, graph-theory, cg.comp-geom, topological-graph-theory
> **Comments:**
> **username_0**: In a [previous question](http://cstheory.stackexchange.com/q/11648/5982) I asked for a method to obtain a dual multigraph. [This answer](http://cstheory.stackexchange.com/a/11649/5982) provides a clear exposition of such a method. Here I am asking for a method to obtain a **simple** dual graph.  
> **username_1**: Some graphs do not have simple duals.  Consider a graph consisting of a single simple path.  This graph has a unique embedding on the sphere, whose dual is a bouquet of circles (and no cellular embedding on any other surface).  
> **username_0**: @JɛﬀE Thanks. I'll try to improve the question.  
> **username_0**: In general, if a graph has a vertex of degree one, there will be a loop in the dual graph, for all embeddings.  

---

## 1 answers

### Answer by username_2 on 2012-06-10. Score: 5 | Accepted answer

For 3-regular graphs, having a simple dual is the same thing as having a polyhedral embedding (an embedding in which each face is a simple cycle and every two faces intersect in an empty set, a vertex, or an edge). But testing for the existence of a polyhedral embedding is known to be NP-complete: see B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, <http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf>

I'm not sure whether polyhedral embeddability is known to remain NP-complete when restricted to 3-regular graphs — it doesn't seem to be in Mohar's paper — but it seems very likely to be true.

> **Comments:**
> **username_0**: I delayed marking this as the answer hoping I could get additional information from other answers. Thanks!  
> **username_0**: Do you know where I can find some more information about polyhedral embeddings? Specifically, it would be nice if I could read an explanation of an algorithm that finds a polyhedral embedding of a graph if there is one. (Perhaps you know how to do it?)  
> **username_0**: related: http://cstheory.stackexchange.com/q/11735/5982  

---

