A bijection for triangulations, quadrangulations, pentagulations, etc

Details A bijection for triangulations, quadrangulations, pentagulations, etc A bijection for triangulations, quadrangulations, pentagulations, etc

2010-07-08

arxiv.org/abs/1007.1292v6

Mathematics

Combinatorics

Scientific paper

A $d$-angulation is a planar map with faces of degree $d$. We present for each integer $d\geq 3$ 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 $d\geq 5$, 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 $d\geq 5$. 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.

Affiliated with

Also associated with

No associations

Rating

A bijection for triangulations, quadrangulations, pentagulations, etc does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A bijection for triangulations, quadrangulations, pentagulations, etc, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A bijection for triangulations, quadrangulations, pentagulations, etc will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-102361