Finding a dual of a graph
Does your dual have to be of minimum genus? Because it's trivial to find a cellular embedding for any graph: just choose a circular ordering for the edges incident to each vertex, arbitrarily, and then determine the faces of the embedding as the sequences of edges consistent with the chosen orderings.

I like the GEM (graph-encoded map) representation of an embedding from the book Foundations of Topological Graph Theory by Bennington and Little. In this representation, an embedding is represented by a 3-edge-colored 3-regular graph with one vertex for every flag of the embedding (an incident triple of vertex, edge, and face) and one edge for every two flags that differ in only one of the elements of the vertex/edge/face sets that they represent. For instance, the image below from Wikipedia can be interpreted as a GEM of a regular dodecahedron, in which the red cycles represent its faces, the yellow cycles represent its edges, and the blue cycles represent its vertices; the edges may be colored according to the colors of their two incident faces.



Given a circular ordering of the edges of a graph G, its GEM can be found by making a cycle of 2d vertices for each degree-d vertex of G, two for each edge, with the pairs of vertex for each incident edge occurring in the cycle in the chosen circular order, and then for each edge e of G linking the two pairs of GEM edges for the two endpoints of e into a rectangle. If you want an oriented embedding the choice of how to link these four vertices into a rectangle should be consistent with the circular orderings, otherwise it can be arbitrary.

Then, the vertices, edges, and faces of the embedding of G are represented by cycles in the GEM that alternate between two of the three edge colors. The dual of G is represented by a GEM with the same underlying 3-regular graph but with two of its edge colors swapped. And the graph represented by a GEM can be formed by contracting all of its vertex cycles and merging pairs of parallel edges into single edges. So constructing a dual of G (as long as you don't care which dual) can easily be done in linear time.