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.