Rooted kernels and Labeled Combinatorial Pyramids

Jocelyn Marchadier &
Luc Brun &
Walter G. Kropatsch.

An irregular pyramid consists of a stack of successively reduced graphs. Each smaller graph is deduced from the preceding one using contraction or removal kernels. A contraction (resp. removal) kernel defines a forest of the initial (resp. dual ) graph, each tree of this forest being reduced to a single vertex (resp. dual vertex) in the reduced graph. A combinatorial map encodes a planar graph thanks to two permutations encoding the edges and their orientation around the vertices. We present in this article a new definition of contraction and removal kernels which allows to encode the different values attached to a given vertex, dual vertex or edge along the pyramid.