###
Hierarchies of Combinatorial Maps

Walter G. Kropatsch &
Luc Brun.
Hierarchies of graphs can be generated by
dual graph contraction. The goal is to reduce
the data structure by a constant reduction
factor while preserving certain image
properties like connectivity. Since these
graphs are typically samplings of the plane
they are by definition plane. The particular
embedding can be represented in different
ways, e.g. a pair of dual graphs relating
points and faces through boundary
segments. Combinatorial maps determine the
embedding by explicitely recording the
orientation of edges around vertices. We
summarize the formal framework which has been
set up to perform dual graph contraction with
combinatorial maps. Contraction is controlled
by kernels that can be combined in many
ways. We have shown that kernels producing a
slow reduction rate can be combined to speed
up reduction. Or, conversely, kernels
decompose into smaller kernels that generate a
more gradual reduction.