Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T01:41:17.965Z Has data issue: false hasContentIssue false

Planar Maps are Well Labeled Trees

Published online by Cambridge University Press:  20 November 2018

Robert Cori
Affiliation:
Université de Bordeaux I, Talence, France
Bernard Vauquelin
Affiliation:
Université de Bordeaux I, Talence, France
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In the theory of enumeration, the part devoted to the counting of planar maps gives rather surprising results. Of special interest to the combinatorialists is the conspicuous feature of counting numbers associated with families of maps as discussed in the papers of Tutte, Brown and Mullin. These formulas are by no means easy to prove; this is also a part of their charm. We are convinced therefore that these maps possess deep combinatorial properties. We discuss such properties in this paper.

The main result of this article is the construction of a bisection between planar maps and a special family of trees: their vertices are labeled with numbers that differ by at most 1 on adjacent vertices. These trees are said to be well labeled. Combinatorialists usually claim that theorems specifying the “geometry” of objects lead to enumerating formulas. Our result obeys this general rule: we can indeed obtain a new proof of the formula counting the number of rooted planar maps with m edges. Four different proofs of this formula are known to date.

Information

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1981