author = {Luc {B}run and Walter {K}ropatsch}, title = {Contraction Kernels and Combinatorial Maps}, booktitle = {$3^{rd}$ IAPR-TC15 Workshop on Graph-based Representations in Pattern Recognition}, pages = {12-21}, year = 2001, editor = {{J}olion, Jean Michel and Walter Kropatsch and Mario Vento}, address = {Ischia Italy}, month = {May}, organization = {IAPR-TC15}, publisher = {CUEN}, theme = {hierarchical}, url = {slides:=https://brunl01.users.greyc.fr/ARTICLES/slides_gbr2001_1.ppt}, abstract = "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."