New bijective links on planar maps via orientations

作者：Fusy Eric^*

来源：European Journal of Combinatorics, 2010, 31(1): 145-160.

DOI：10.1016/j.ejc.2009.02.008

This article presents new bijections on planar maps. At first a bijection is established between bipolar orientations on planar maps and specific "transversal structures" on triangulations of the 4-gon with no separating 3-cycle, which are called irreducible triangulations. This bijection specializes to a bijection between rooted non-separable maps and rooted irreducible triangulations. This yields in turn a bijection between rooted loopless maps and rooted triangulations, based on the observation that loopless maps and triangulations are decomposed in a similar way into components that are respectively non-separable mps and irreducible triangulations. This gives another bijective proof (after Wormald's construction published in 1980) of the fact that rooted loopless maps with n edges are equinumerous to rooted triangulations with it inner vertices.

• 出版日期2010-1