A bijection for triangulations, quadrangulations, pentagulations, etc.

DOI10.1016/J.JCTA.2011.08.006MaRDI QIDQ645974zbMATH OpenOpenAlexFDO

Authors Olivier Bernardi, Éric Fusy

Publication date 11 November 2011

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1007.1292

zbMATH Keywords

countingmaster bijectiond-angulationsmaps with boundariesunified bijections

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Combinatorial identities, bijective combinatorics (05A19)

Abstract: A $d$-angulation is a planar map with faces of degree $d$. We present for each integer $dgeq3$ a bijection between the class of $d$-angulations of girth $d$ (i.e., with no cycle of length less than $d$) and a class of decorated plane trees. Each of the bijections is obtained by specializing a "master bijection" which extends an earlier construction of the first author. Our construction unifies known bijections by Fusy, Poulalhon and Schaeffer for triangulations ($d=3$) and by Schaeffer for quadrangulations ($d=4$). For $dgeq5$, both the bijections and the enumerative results are new. We also extend our bijections so as to enumerate emph{$p$-gonal $d$-angulations} ($d$-angulations with a simple boundary of length $p$) of girth $d$. We thereby recover bijectively the results of Brown for simple $p$-gonal triangulations and simple $2p$-gonal quadrangulations and establish new results for $dgeq5$. A key ingredient in our proofs is a class of orientations characterizing $d$-angulations of girth $d$. Earlier results by Schnyder and by De Fraysseix and Ossona de Mendez showed that simple triangulations and simple quadrangulations are characterized by the existence of orientations having respectively indegree 3 and 2 at each inner vertex. We extend this characterization by showing that a $d$-angulation has girth $d$ if and only if the graph obtained by duplicating each edge $d-2$ times admits an orientation having indegree $d$ at each inner vertex.

Recommendations

• A bijection for triangulations of a polygon with interior points and multiple edges
• A bijection between the triangulations of convex polygons and ordered trees
• A bijection for essentially 4-connected toroidal triangulations
• A bijection for tricellular maps
• A geometric bijection between a family of hypermaps and a family of polygons enumerated by the series of Schröder
• scientific article; zbMATH DE number 1741019
• A bijection for plane graphs and its applications
• A bijection between 2-triangulations and pairs of non-crossing Dyck paths
• Bijections for planar maps with boundaries
• scientific article; zbMATH DE number 2077656

Cites work

• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• A Census of Planar Maps
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• Analytic combinatorics
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Blocked edges on Eulerian maps and mobiles: application to spanning trees, hard particles and the Ising model
• Census of planar maps: From the one-matrix model solution to a combinatorial proof
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• Enumeration of Quadrangular Dissections of the Disk
• Enumeration of Triangulations of the Disk
• Lattice structures from planar graphs
• On topological aspects of orientations
• Optimal coding and sampling of triangulations
• Planar Maps are Well Labeled Trees
• Planar graphs and poset dimension
• Planar maps as labeled mobiles
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• Schnyder decompositions for regular plane graphs and application to drawing
• Unified bijections for maps with prescribed degrees and girth

Cited in

(28)

• Spanning forests in regular planar maps
• Blossoming bijection for higher-genus maps
• A note on irreducible maps with several boundaries
• Unified bijections for maps with prescribed degrees and girth
• Simple formulas for constellations and bipartite maps with prescribed degrees
• Large expanders in high genus unicellular maps
• Bijections for planar maps with boundaries
• Orientations and bijections for toroidal maps with prescribed face-degrees and essential girth
• Bijective proof of the rationality of the generating series of higher-genus maps
• On polynomials counting essentially irreducible maps
• Simple formulas for constellations and bipartite maps with prescribed degrees
• Bijections for generalized Tamari intervals via orientations
• Bijections for generalized Tamari intervals via orientations
• Growing uniform planar maps face by face
• Maps of unfixed genus and blossoming trees
• Irreducible metric maps and Weil-Petersson volumes
• scientific article; zbMATH DE number 844159 (Why is no real title available?)
• On irreducible maps and slices
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• A bijection for essentially 3-connected toroidal maps
• Schnyder decompositions for regular plane graphs and application to drawing
• Asymptotic expansions for sub-critical Lagrangean forms
• Contact Graphs of Circular Arcs
• A generic method for bijections between blossoming trees and planar maps
• A bijection for essentially 4-connected toroidal triangulations
• Counting colored planar maps: algebraicity results
• Complex parametrization of triangulations on oriented maps
• Flip distances between graph orientations

This page was built for publication: A bijection for triangulations, quadrangulations, pentagulations, etc.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q645974)