Slit-slide-sew bijections for bipartite and quasibipartite plane maps

Jérémie Bettinelli¹

¹Ecole Polytechnique

The electronic journal of combinatorics, Tome 27 (2020) no. 3

Résumé

We unify and extend previous bijections on plane quadrangulations to bipartite and quasibipartite plane maps. Starting from a bipartite plane map with a distinguished edge and two distinguished corners (in the same face or in two different faces), we build a new plane map with a distinguished vertex and two distinguished half-edges directed toward the vertex. The faces of the new map have the same degree as those of the original map, except at the locations of the distinguished corners, where each receives an extra degree: this is the location of the distinguished half-edges. This bijection provides a sampling algorithm for uniform maps with prescribed face degrees and allows to recover Tutte's famous counting formula for bipartite and quasibipartite plane maps. In addition, we explain how to decompose the previous bijection into two more elementary ones, which each transfer a degree from one face of the map to another face. In particular, these transfer bijections are simpler to manipulate than the previous one and this point of view simplifies the proofs.

Détail

DOI : 10.37236/9069

Classification : 05C30, 05C05, 05C10, 57N16, 60D05
Mots-clés : bijections on plane quadrangulations, Tutte's counting formula