DIMACS TR: 96-35

Dual Graphs on Surfaces

Author: Vladimir Gurvich


Consider an embedding of a graph $G$ in a surface $S$ ({\it map}). Assume that the difference splits into connected components ({\it 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-to-one correspondence between their edge-sets. An arbitrary pair of graphs with common set of edges is called a {\it plan}. Every map induces a plan. A plan is called {\it \bf 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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-35.ps.gz
DIMACS Home Page