# 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. – becko Jun 10 '12 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). – Jeffε Jun 10 '12 at 2:13
• @JɛﬀE Thanks. I'll try to improve the question. – becko Jun 10 '12 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. – becko Jun 10 '12 at 2:25