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.