# Finding a simple dual of a simple graph in some surface

Given a cellular embedding 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.

• In a previous question I asked for a method to obtain a dual multigraph. This answer provides a clear exposition of such a method. Here I am asking for a method to obtain a simple dual graph. Jun 10, 2012 at 0:23
• 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). Jun 10, 2012 at 2:13
• @JɛﬀE Thanks. I'll try to improve the question. Jun 10, 2012 at 2:17
• In general, if a graph has a vertex of degree one, there will be a loop in the dual graph, for all embeddings. Jun 10, 2012 at 2:25