DIMACS TR: 96-35
Dual Graphs on Surfaces
Author: Vladimir Gurvich
ABSTRACT
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