Growing uniform planar maps face by face

Alessandra Caraceni*, Alexandre Stauffer

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

We provide “growth schemes” for inductively generating uniform random 2p-angulations of the sphere with n faces, as well as uniform random simple triangulations of the sphere with 2n faces. In the case of 2p-angulations, we provide a way to insert a new face at a random location in a uniform 2p-angulation with n faces in such a way that the new map is precisely a uniform 2p-angulation with n + 1 faces. Similarly, given a uniform simple triangulation of the sphere with 2n faces, we describe a way to insert two new adjacent triangles so as to obtain a uniform simple triangulation of the sphere with 2n + 2 faces. The latter is based on a new bijective presentation of simple triangulations that relies on a construction by Poulalhon and Schaeffer.
Original languageEnglish
Pages (from-to)942-967
JournalRandom Structures and Algorithms
Volume63
Issue number4
Early online date19 Jun 2023
DOIs
Publication statusPublished - Dec 2023

Keywords

  • random generation
  • random planar maps
  • random trees
  • triangulations

Fingerprint

Dive into the research topics of 'Growing uniform planar maps face by face'. Together they form a unique fingerprint.

Cite this