Dual Graphs on Surfaces
Vladimir A. Gurvich · 1996
Consider an embedding of a graph 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 graph 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-toone 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. We also give an algorithm of reconstruction a map from a geographic plan. A case when this map is unique is singled out. Partially, these results were announced by Gurvich and Shabat in 1989.