A bijection for triangulations, quadrangulations, pentagulations, etc.

DOI10.1016/J.JCTA.2011.08.006zbMATH Open1232.05019arXiv1007.1292OpenAlexW2089947338MaRDI QIDQ645974FDOQ645974

Authors: Olivier Bernardi, Éric Fusy 

Publication date: 11 November 2011

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

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.

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

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

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)

Cites Work

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

Cited In (29)

• Blossoming bijection for higher-genus maps
• Spanning forests in regular planar 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
• On irreducible maps and slices
• Bijections for planar maps with boundaries
• A new family of bijections for planar maps
• 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
• Simple formulas for constellations and bipartite maps with prescribed degrees
• On polynomials counting essentially irreducible maps
• 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
• Title not available (Why is that?)
• Irreducible metric maps and Weil-Petersson volumes
• A bijection for essentially 3-connected toroidal maps
• A bijection for covered maps, or a shortcut between Harer-Zagiers and Jacksons formulas
• 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
• Flip distances between graph orientations
• Complex parametrization of triangulations on oriented maps

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)