Finding a simple dual of a simple graph in some surface
For 3-regular graphs, having a simple dual is the same thing as having a polyhedral embedding (an embedding in which each face is a simple cycle and every two faces intersect in an empty set, a vertex, or an edge). But testing for the existence of a polyhedral embedding is known to be NP-complete: see B. Mohar, Existence of polyhedral embeddings of graphs, Combinatorica 21 (2001), 395–401, http://www.fmf.uni-lj.si/~mohar/Papers/Fw3npc.pdf

I'm not sure whether polyhedral embeddability is known to remain NP-complete when restricted to 3-regular graphs — it doesn't seem to be in Mohar's paper — but it seems very likely to be true.