Planar Maps as Labeled Mobiles

We extend Schaeffer's bijection between rooted quadrangulations and well-labeled trees to the general case of Eulerian planar maps with prescribed face valences to obtain a bijection with a new class of labeled trees, which we call mobiles. Our bijection covers all the classes of maps previousl...

Full description

Saved in:
Bibliographic Details
Published in:The Electronic journal of combinatorics 2004-09, Vol.11 (1)
Main Authors: Bouttier, J., Di Francesco, P., Guitter, E.
Format: Article
Language:English
Subjects:
Combinatorics
Condensed Matter
Mathematics
Physics
Statistical Mechanics
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We extend Schaeffer's bijection between rooted quadrangulations and well-labeled trees to the general case of Eulerian planar maps with prescribed face valences to obtain a bijection with a new class of labeled trees, which we call mobiles. Our bijection covers all the classes of maps previously enumerated by either the two-matrix model used by physicists or by the bijection with blossom trees used by combinatorists. Our bijection reduces the enumeration of maps to that, much simpler, of mobiles and moreover keeps track of the geodesic distance within the initial maps via the mobiles' labels. Generating functions for mobiles are shown to obey systems of algebraic recursion relations.
ISSN:1077-8926
1077-8926
DOI:10.37236/1822