According to the book Topological Graph Theory by Gross and Tucker, given a cellular embedding 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.