A model of trees for 5-connected planar triangulations
Éric Fusy ∗ · 2025
Read A model of trees for 5-connected planar triangulations by Éric Fusy ∗ (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-24420.txt.
Introduction
Éric Fusy builds a tree model for five connected planar triangulations, working alone. He studies triangulations of a pentagon with no separating triangle or quadrangle, called 5c-triangulations, a family closely tied to 5-connected planar triangulations. Such highly connected maps are hard to count and generate directly.
Fusy proves these triangulations correspond one to one with five regular plane trees obeying a simple local rule at inner edges. The bijection yields explicit generating functions for rooted cases, in the same algebraic extension as a known result by Gao, Wanless, and Wormald. It also gives efficient uniform random generation and compact encoding methods for these maps.
Catalog record
| CREATOR | Éric Fusy ∗ |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 75 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-24420
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A model of trees for 5-connected planar triangulations Thanks: ∗ LIGM, CNRS, Univ Gustave Eiffel, ESIEE Paris, F-77454 Marne-la-Vallée, France, [email protected] Éric Fusy ∗ Abstract . Triangulations of the 5-gon with no separating triangle nor quadrangle, so called 5c-triangulations, are a planar map family closely related to 5-connected planar triangulations. We show that 5c-triangulations are in bijection with 5-regular plane trees satisfying a simple local constraint at inner edges. It yields explicit expressions for the generating functions of rooted 5c-triangulations, and of rooted 5-connected planar triangulations with root-vertex degree 5, these belonging to the same algebraic extension as the generating function of rooted 5-connected planar triangulations computed by Gao, Wanless and Wormald. The bijection also makes it possible to obtain efficient uniform random generation and succinct encoding procedures for 5-connected planar triangulations. 1. Introduction A rich literature is devoted to the enumeration of (rooted) planar maps, initiated by the pioneering work of Tutte [ Tut62 , Tut63 ] . The original method proceeded by showing that the generating function —with an additional catalytic variable— satisfies a functional equation, obtained typically by translating a decomposition by root deletion, and then solving the functional equation either by guessing-checking, or by the quadratic method [ Tut73 ] and its extensions [ BJ06 , Eyn16 ] . Another fruitful approach is to relate families of maps via substitution schemes [ Tut63 , MS68 , BFSS01 , GWW01 , BG14 ] , allowing to extract expressions for the generating functions of map families with higher connectivity/girth constraints (whereas catalytic equations for such families are often more difficult to obtain). Various families of planar maps can be enumerated by these methods, yielding surprisingly simple counting formulas. Other map enumeration approaches have been developed, in particular matrix integral techniques [ DFGZJ95 ] , and closer to our focus, bijective constructions that provide direct combinatorial proofs of the counting formulas, starting with the Cori-Vauquelin bijection [ CV81 ] , and further developed by Schaeffer [ Sch98 ] and by Bouttier, Di Francesco and Guitter [ BDFG02 , BDFG04 ] . Bijective methods for planar maps have gained a high level of generality over the years, and one can essentially distinguish three main methods: (i): Bijections that are obtained by showing that each map from the considered family can be endowed with a canonical orientation (or, more generally, a canonical weighted biorientation), typically with properties of minimality (no clockwise cycle), accessibility (from any vertex one can reach the root-face or root-vertex), and specification of vertex outdegrees and face degrees; one can then specialize a general bijection (keeping track of vertex outdegrees and face degrees) that encodes a minimal accessible orientation by a decorated plane tree. Two different such general bijections were provided respectively in [ BF12a ] and in [ AP15 ] . These gave a unified setting encompassing most bijections that were known for planar map families, and making it possible to obtain extensions such as the enumeration of planar maps of fixed girth with control on the face-degrees [ BF12b ] . (ii): Slice decompositions [ BG12 ] , where the considered maps are cut along certain geodesic paths, yielding a decomposition into slice-maps, and slice-maps are themselves recursively decomposed, again by cutting along certain geodesic paths. As (i) this method is well suited for the enumeration of maps with control on the girth and face-degrees [ BG14 , BGM24 ] , with extension to the so-called irreducible setting. (iii): A recent bijective construction [ DS25 ] turns (via certain rewiring operations) the description trees given by a generic order-one catalytic equation into trees that are specified by a context-free grammar. This establishes a bridge from Tutte’s method to a bijective encoding of maps by trees that are easy to count. In this paper we consider the class of so-called 5c-triangulations , i.e., triangulations of the 5-gon with no separating triangle nor separating quadrangle 1 1 1 In a planar map a cycle is called separating if there is at least one vertex inside and at least one vertex outside (the underlying graph is thus disconnected by deletion of the cycle). . These have been recently considered in [ BFL25 , Sec.12] , [ BFL23 ] , where it is proved that these maps are characterized by the existence of Schnyder-type combinatorial structures that admit several incarnations: as corner labelings, as certain woods on 5 trees, or as outdegree-constrained orientations on the primal-dual map (in [ BFL23 ] it is also shown that the wood incarnation yields a face-counting crossing-free straight-line drawing algorithm). These maps are also closely related to 5-connected planar triangulations, which are known to be the triangulations with no separating triangle nor separating quadrangle. The enumeration of rooted 5-connected planar triangulations has been solved by Gao, Wanless and Wormald [ GWW01 ] via a bivariate application of the substitution method, yielding an explicit algebraic expression for the generating function. No bijection by the above mentioned methods was known for 5-connected planar triangulations, whereas methods (i) and (ii) are known to apply [ Fus09 , BG14 ] to triangulations of the 4-gon with no separating triangle —called irreducible— which are closely related to 4-connected planar triangulations. Our main contribution is to exhibit a simple family of trees that are in bijection to 5c-triangulations. A plane tree is an unrooted tree embedded in the plane. The non-leaf vertices are called nodes , the edges incident to a leaf are called legs , while the other ones are called inner edges . A k -regular plane tree is a plane tree such that all nodes have degree k . It is called leg-balanced if for every inner edge, one of its two half-edges is followed by a leg in clockwise order around the incident node, while the other half-edge is followed by an inner edge. The following is our main result (see Figure 1 ): Figure 1. Left: a 5c-triangulation. Right: the corresponding leg-balanced 5-regular plane tree. Theorem 1.1 . There is an explicit bijection \phi between 5c-triangulations with n\!+\!5 vertices and leg-balanced 5-regular plane trees with n nodes, for n\geq 1 . Let us note that bijective constructions are already known to relate k -connected triangulations to (sub-)families of k -regular plane trees for k\in\{3,4\} . Precisely, 3-connected (i.e., simple) plane triangulations with n+3 vertices are in bijection with 3 -regular plane trees —with nodes properly bicolored— having n white nodes and such that all leaves are adjacent to black nodes [ FPS08 , BF12a ] . And triangular dissections of the 4-gon with no separating triangle (called irreducible triangulations of the 4-gon, these are closely related to 4-connected triangulations) having n+4 vertices are in bijection with 4 -regular plane trees having n nodes [ Fus09 ] . The bijection of Theorem 1.1 thus extends this pattern to k=5 . Outline. Our bijection \phi follows the scheme (i) and is close to the bijection of [ FPS08 ] for irreducible quadrangulations of the hexagon, which relies on a certain biorientation of the inner edges, called here a tree-biorientation . Precisely it is shown in [ FPS08 ] that irreducible quadrangulations of the hexagon are characterized by the existence of a (unique) tree-biorientation with all inner vertices