  We introduce and study the problem \mpd, which asks for two planar graphs
$G_1$ and $G_2$ whether $G_1$ can be embedded such that its dual is isomorphic
to $G_2$. Our algorithmic main result is an NP-completeness proof for the
general case and a linear-time algorithm for biconnected graphs. To shed light
onto the combinatorial structure of the duals of a planar graph, we consider
the \emph{common dual relation} $\sim$, where $G_1 \sim G_2$ if and only if
they have a common dual. While $\sim$ is generally not transitive, we show that
the restriction to biconnected graphs is an equivalence relation. In this case,
being dual to each other carries over to the equivalence classes, i.e., two
graphs are dual to each other if and only if any two elements of their
respective equivalence classes are dual to each other.
  To achieve the efficient testing algorithm for \mpd on biconnected graphs, we
devise a succinct representation of the equivalence class of a biconnected
planar graph. It is similar to SPQR-trees and represents exactly the graphs
that are contained in the equivalence class. The testing algorithm then works
by testing in linear time whether two such representations are isomorphic. We
note that a special case of \mpd is testing whether a graph $G$ is self-dual.
Our algorithm handles the case where $G$ is biconnected and our NP-hardness
proof extends to testing self-duality of general planar graphs and also to
testing map self-duality, where a graph $G$ is map self-dual if it admits a
planar embedding $\mathcal G$ such that $G^\star$ is isomorphic to $G$, and
additionally the embedding induced by $\mathcal G$ on $G^\star$ is $\mathcal
G$.
