Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-22T03:55:34.804Z Has data issue: false hasContentIssue false
  • English
  • Français

Planar Maps are Well Labeled Trees

Published online by Cambridge University Press:  20 November 2018

Robert Cori  and
Bernard Vauquelin
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.

Type
Research Article
Information
Canadian Journal of Mathematics , Volume 33 , Issue 5 , 01 October 1981 , pp. 1023 - 1042
Copyright
Copyright © Canadian Mathematical Society 1981

References

1. Cartier, P. and Foata, D., Problèmes combinatoires de commutation et rearrangement, Lecture Notes in Math. 55 (Springer-Verlag, Berlin, 1969).Google Scholar
2. Cori, R., Un code pour les graphes planaires et ses applications, Astérisque, Société Math, de France 27 (1975).Google Scholar
3. Cori, R. and Richard, J., Enumeration des graphes planaires à l'aide de séries formelles en variables non commutatives, Discrete Math. 2 (1972), 115–162.Google Scholar
4. de Bruijn, N. G. and Morselt, B. J. M., A note on plane trees, J. Combinatorial Theory 2 (1967), 27–34.Google Scholar
5. Edmonds, J., Combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), 646.Google Scholar
6. Foata, D. and Schûtzenberger, M. P., Théorie géométrique des polynômes eulériens, Lecture Notes in Math. 138 (Springer-Verlag, Berlin, 1970).Google Scholar
7. Jacques, A., Sur le genre d'une paire de substitutions, C. R. Acad. Sci. Paris 267 (1968), 625–627.Google Scholar
8. Jacques, A., Constellations et graphes topologiques in Combinatorial theory and its applications, Colloq. Math. Soc. Janos Bolyai (North Holland Amsterdam, 1970), 657–672.Google Scholar
9. Klarner, D. A., Correspondance between plane tree and binary sequences, J. Comb. Theory 9 (1970), 401–411.Google Scholar
10. Lehman, A. B., A bijective census of rooted planar maps, Communication at Ontario Math. Conference (1970), unpublished.Google Scholar
11. Raney, G. N., Functional composition patterns and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441–451.Google Scholar
12. Read, R. C., The coding of various kinds of unlabeled trees in Graph theory and computing (Academic Press, New York, 1972), 153–182.Google Scholar
13. Tutte, W. T., A census of slicings, Can. J. Math. 14 (1962), 708–722.Google Scholar
14. Tutte, W. T., A census of planar maps, Can. J. Math. 15 (1963), 249–271.Google Scholar
15. Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc. 74 (1968), 64–74.Google Scholar
16. Walsh, T. S. and Lehman, A. B., Counting rooted maps by genus I and II, J. Comb. Theory 13B (1972), 192–218 and 122-141.Google Scholar