  Given two graphs $G$ and $G^*$ with a one-to-one correspondence between their
edges, when do $G$ and $G^*$ form a pair of dual graphs realizing the vertices
and countries of a map embedded in a surface? A criterion was obtained by Jack
Edmonds in 1965. Furthermore, let $\boldsymbol{d}=(d_1,\ldots,d_n)$ and
$\boldsymbol{t}=(t_1,\ldots,t_m)$ be their degree sequences. Then, clearly,
$\sum_{i=1}^n d_i = \sum_{j=1}^m t_j = 2\ell$, where $\ell$ is the number of
edges in each of the two graphs, and $\chi = n - \ell + m$ is the Euler
characteristic of the surface. Which sequences $\boldsymbol{d}$ and
$\boldsymbol{t}$ satisfying these conditions still cannot be realized as the
degree sequences? We make use of Edmonds' criterion to obtain several infinite
series of exceptions for the sphere, $\chi = 2$, and projective plane, $\chi =
1$. We conjecture that there exist no exceptions for $\chi \leq 0$.
