###
Contraction Kernels and Combinatorial Maps

Luc Brun &
Walter Kropatsch.
Graph pyramids are made of a stack of successively
reduced graphs embedded in the plane. Such pyramids
overcome the main limitations of their regular
ancestors. The graphs used in the pyramid May be
region adjacency graphs, dual graphs or
combinatorial maps. Compared to the usual graph data
structures, combinatorial maps offer an explicit
encoding of the orientation of edges around
vertices. Each combinatorial map in the pyramid is
generated from the one below by a set of edges to be
contracted. This contraction process is controlled
by kernels that can be combined in many ways. We
show in this paper, 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. We also propose one sequential and one
parallel algorithm to compute the contracted
combinatorial maps defined by kernels.