Rooted Kernels and Labeled Combinatorial Pyramids ∗
Jocelyn Marchadier, Luc Brun, Walter G. Kropatsch · 2004
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. 1