A Master Bijection for Planar Maps, and Its Applications

  • Olivier Bernardi | MIT

Planar maps are embeddings of connected planar graphs in the plane considered up to continuous deformation. We will present a “master bijection” for planar maps and show that it can be specialized in various ways in order to count several families of maps. More precisely, for each integer d we obtain a bijection between the family of maps of girth d and a family of decorated plane trees. This gives new counting results for maps of girth d counted according to the degree distribution of their faces. Our approach unifies and extends many known bijections. A key ingredient in the proofs are classes of orientations generalizing Schnyder woods.

This is a joint work with Eric Fusy.

Speaker Details

Olivier Bernardi is an Instructor in Applied Mathematics at MIT (on leave from the CNRS, Paris.). He obtained his Ph.D. in computer science at Universite Bordeaux (LaBRI) on Combinatorics of maps and the Tutte polynomial, supervised by Mireille Bousquet-Melou, in 2006.

Watch Next