Dual graphs on surfaces

Consider an embedding of a graphs G in a surface S (map). Assume that the difference splits into connected components (countries), each one homeomorphic to an open disk. (It follows from this assumption that graphs G must be connected). Introduce a graph G* dual to G realizing the neighbor relations among countries. The graphs G and G* have the same set of edges. More precisely, there is a natural one-to-one correspondence between their edge-sets. An arbitrary pair of graphs with common set of edges is called a plan. Every map induces a plan. A plan is called geographic if it is induced by a map. In terms of Eulerian graphs we obtain criteria for a plan to be geographic. Partially, these results were announced by Vladimir Gurvich and George Shabat. Charts of Surfaces and their Schemes, Soviet Math. Dokl. 39:2 (1989) 390-394.