# Bijective enumeration of planar bipartite maps with three tight boundaries,
or how to slice pairs of pants

Jérémie Bouttier Université Paris-Saclay, CNRS, CEA, Institut de physique
théorique, 91191, Gif-sur-Yvette, FranceUniv Lyon, Ens de Lyon, Univ Claude
Bernard, CNRS, Laboratoire de Physique, F-69342 Lyon Emmanuel
Guitter11footnotemark: 1 Grégory Miermont ENS de Lyon, UMPA, CNRS UMR 5669, 46
allée d’Italie, 69364 Lyon Cedex 07, France

###### Abstract

We consider planar maps with three boundaries, colloquially called pairs of
pants. In the case of bipartite maps with controlled face degrees, a simple
expression for their generating function was found by Eynard and proved
bijectively by Collet and Fusy. In this paper, we obtain an even simpler
formula for _tight_ pairs of pants, namely for maps whose boundaries have
minimal length in their homotopy class. We follow a bijective approach based
on the slice decomposition, which we extend by introducing new fundamental
building blocks called bigeodesic triangles and diangles, and by working on
the universal cover of the triply punctured sphere. We also discuss the
statistics of the lengths of minimal separating loops in (non necessarily
tight) pairs of pants and annuli, and their asymptotics in the large volume
limit.

###### Contents

  1. 1 Introduction
  2. 2 Basic building blocks
    1. 2.1 Preliminaries: geodesics and related concepts
    2. 2.2 Tight slices
    3. 2.3 Bigeodesic diangles
    4. 2.4 Bigeodesic triangles
  3. 3 Assembling the building blocks
    1. 3.1 Description of the assembling procedures I and II
    2. 3.2 Properties of the assembling procedures
    3. 3.3 Enumerative consequences
    4. 3.4 Disassembling a triply pointed map
  4. 4 The universal cover of a map with three boundaries
    1. 4.1 Construction and properties of the universal cover
    2. 4.2 Visualizing the assembling procedures on the universal cover
    3. 4.3 Tightness of the boundaries resulting from the assembling procedures
  5. 5 Decomposing a map with three tight boundaries
    1. 5.1 Graph-theoretical properties of the universal cover
    2. 5.2 Infinite geodesics and Busemann functions
    3. 5.3 Busemann functions associated with tight boundaries
    4. 5.4 Leftmost bigeodesics and the diangle lemma
    5. 5.5 Equilibrium vertices and the triangle lemma
    6. 5.6 Decomposing a map of type I
    7. 5.7 Decomposing a map of type II
  6. 6 Equivalence with the Eynard-Collet-Fusy formula, and limiting statistics in random maps with boundaries
    1. 6.1 The structure of outermost minimal separating cycles
    2. 6.2 A re-derivation of the ECF formula for pairs of pants
    3. 6.3 Scaling limits of separating loop statistics
  7. 7 Conclusion
  8. A A slice-theoretic enumeration of triply pointed maps
  9. B Connection with well-labeled maps

##  1 Introduction

#### Context and motivations.

The study of maps (graphs embedded into surfaces) is an active field of
research, at the crossroads between combinatorics, theoretical physics and
probability theory. The combinatorial theory of maps started with the
pioneering work of Tutte in the 1960’s [Tut68], and we refer to the recent
review by Schaeffer [Sch15] for an account of its many developments ever
since. In theoretical physics, maps are intimately connected with matrix
models and two-dimensional quantum gravity: see for instance the review by Di
Francesco, Ginsparg and Zinn-Justin [DFGZJ95], the book by Ambjørn, Durhuus
and Jonsson [ADJ97], and the book by Eynard [Eyn16] for more recent
mathematical advances including the theory of topological recursion.
Probability theory aims at understanding the geometric properties of large
random maps and their limits: this topic is covered in several sets of lecture
notes [LGM12, Mie14, Bud17, Cur19], and we also mention the review by Miller
[Mil18] which discusses the connection with Liouville quantum gravity, a
rigorous approach to two-dimensional quantum gravity.

A key tool in the study of maps is the _bijective approach_ , which consists
in finding correspondences between different families of maps, or with other
combinatorial objects such as trees or lattice walks. Bijections often yield
elementary derivations of enumerative results, but are also useful to
understand properties of maps such as distances (see the aforementioned
references). There exists by now several general bijective frameworks, and in
this paper we focus on a specific one, called the slice decomposition.

Colloquially speaking, the  _slice decomposition_ consists in performing a
canonical decomposition of maps, by cutting them along leftmost geodesics. It
was first mentioned in the papers [BG09b, BG12, AB12], mostly as a
reformulation of the decomposition of mobiles [BDFG04]. Its real significance
was highlighted in the paper [BG14]—see also [Bou19, Chapter 2] for a recent
exposition—which considers so-called irreducible maps for which bijections
were not known before. The slice decomposition also passes naturally to the
scaling limit [LG13, BM17]. However, it has so far been understood only in the
case of _disks_ and _annuli_ , namely planar maps with one or two boundaries.
Our purpose is to understand the case of maps with other topologies, with the
long-term goal of developing a bijective approach to topological recursion.

In this paper, we make a first step in this direction, by considering _pairs
of pants_ , namely planar maps with three boundaries. For simplicity, we
restrict to the case of bipartite maps with controlled face degrees (also
known as Boltzmann maps), though we believe that our treatment can be extended
to the non bipartite or to the irreducible settings as considered in [BG12,
BG14]. A simple explicit expression of the generating function of bipartite
pairs of pants was given by Eynard [Eyn16, Proposition 3.3.1] and derived
bijectively by Collet and Fusy [CF12]. Here, we obtain an even simpler formula
for _tight_ pairs of pants, namely for maps whose boundaries have minimal
length in their homotopy class. As we shall see, our formula is equivalent to
the Eynard-Collet-Fusy formula, but our derivation is fundamentally different.

Our approach consists in decomposing tight pairs of pants into geometric
pieces which we call (bigeodesic) diangles and triangles. While the former
are, in a sense, generalizations of the existing notion of slices, the second
are new objects (although they appear implicitly in earlier work [BG08], see
the discussion in Appendix B). As was pointed to us by Bram Petri, the way in
which the elementary pieces are assembled is very much reminiscent of
classical constructions of pairs of pants in hyperbolic geometry from ideal
hyperbolic triangles, see for instance [Thu97, Section 3.4]. In particular,
some notions of importance in this paper, which we refer to as “equilibrium
vertices” in triangles and “exceedances” in diangles, have natural analogs in
hyperbolic geometry: the equilibrium vertices correspond to tangency points of
the inner circles of the ideal triangles, and the exceedances correspond to
the invariants $d(v)$ in [Thu97].

We believe that many other connections exist between these classical concepts
and our work. In particular, in the context of the classification of Riemann
and hyperbolic surfaces [IT92], pants decompositions play a fundamental role.
It is therefore natural to expect that similar decompositions should exist in
the context of maps. In particular, the tightness constraint which we
introduce should be an important ingredient: indeed, it should translate the
natural idea of cutting surfaces along closed geodesics, in order to obtain
canonical decompositions. Such pants decompositions will be explored in future
research, but provide one of our main motivations for the present paper.

#### Overview.

A _planar map_ is a connected multigraph embedded into the sphere without edge
crossings, and considered up to homeomorphism. It consists of _vertices_ ,
_edges_ , _faces_ and _corners_ , see [Sch15] for precise definitions. Until
further notice, we only consider finite maps, i.e. maps with a finite number
of edges (hence of vertices, faces and corners). A _path_ on a map is a
sequence of consecutive edges, and the _length_ of a path is its number of
edges. Given a face, its _contour_ is the closed path formed by its incident
edges, and its _degree_ is the length of the contour. A planar map is
_bipartite_ if all its faces have even degree.

A _boundary_ is either a marked face or a marked vertex on the map. We will
use the denominations _boundary-face_ and _boundary-vertex_ when we wish to
specify the nature of a boundary. We define the _length_ of a boundary as
being equal to its degree in the case of a boundary-face, and to zero in the
case of a boundary-vertex. Faces which are not boundaries are called _inner
faces_. A map is said _essentially bipartite_ if all its inner faces have even
degree. The sum of the lengths of the boundaries of an essentially bipartite
map is necessarily even.

Figure 1: An intuitive way to think of a boundary-vertex: we remove a small
disk around it, and keep all incident edges connected along a circle made of
special (dashed) edges, which are considered as having length zero. Note that
a path passing through a boundary-vertex may “circumvent” it in two ways,
which will correspond to different homotopy classes when there are other
boundaries.

We intuitively think of boundaries as representing punctures on the sphere.
This is rather natural in the case of a boundary-face (we just remove its
interior from the surface), but slightly less in the case of boundary-vertex:
see Figure 1. A path on the map, together with a choice of circumventing
direction when passing through a boundary-vertex, corresponds to a path on the
punctured sphere. Two closed paths are said to be in the same _homotopy class_
, or _freely homotopic_ , if they can be continuously deformed into one
another on the punctured sphere. A boundary-face is said _tight_ if its
contour has minimal length in its homotopy class (if the boundary-face is
incident to a boundary-vertex, the contour should be considered as the contour
of the corresponding face in the map modified as in Figure 1). A boundary-
vertex is by convention always tight.

We are interested in essentially bipartite planar maps with three distinct
boundaries which are labeled (distinguishable). Such maps cannot have
symmetries, and therefore we do not root (i.e., mark a corner on) the
boundaries. Two situations may occur: either all the boundary lengths are
even, and the planar map is truely bipartite, or two lengths are odd and the
third is even, and following [CF12] we say that the map is _quasi-bipartite_.
We may now state our main enumerative result:

######  Theorem 1.

Let $a$, $b$ and $c$ be integers or half-integers such that $a+b+c$ is an
integer. Then, the generating function $T_{a,b,c}$ of essentially bipartite
planar maps with three labeled distinct tight boundaries of lengths $2a$,
$2b$, $2c$, counted with a weight $t$ per vertex different from a boundary-
vertex and, for all $k\geq 1$, a weight $g_{2k}$ per inner face of degree
$2k$, is equal to

$T_{a,b,c}=R^{a+b+c}\frac{d\ln R}{dt}-t^{-1}\mathbf{1}_{a=b=c=0}$ (1)

where $R$ is the formal power series in $t,g_{2},g_{4},\ldots$ determined by

$R=t+\sum_{k\geq 1}\binom{2k-1}{k}g_{2k}R^{k}$ (2)

and where $\mathbf{1}_{P}$ is equal to $1$ if $P$ is true, and to $0$
otherwise.

Figure 2: The possible types of maps with three tight boundaries and no inner
face. Tightness implies that there are no vertices of degree one, except
possibly boundary-vertices, indicated here by blue crosses. To identify the
different types, assume without loss of generality that the boundary lengths
are $b\geq a\geq c$. There exists two generic situations, denoted I and II,
corresponding to the cases $b<a+c$ and $b>a+c$ respectively. The degenerate
cases correspond to having $b=a+c$ or/and some lengths equal to zero. We may
check that there are $a+b+c-1$ vertices different from boundary-vertices in
all cases.

It is not difficult to check that the right-hand side of (1) is indeed a well-
defined power series in $t,g_{2},g_{4},\ldots$. It is useful to look first at
the case where $g_{2},g_{4},\ldots$ all vanish. This corresponds to maps
without inner faces. In this case, $T_{0,0,0}$ vanishes while, for $a,b,c$ not
all zero, $T_{a,b,c}$ is equal to $t^{a+b+c-1}$: this means that there should
exist exactly one such map, with $a+b+c-1$ vertices different from boundary-
vertices. This is indeed true, as illustrated on Figure 2.

Our expression for $T_{a,b,c}$ is very similar to the aforementioned Eynard-
Collet-Fusy (ECF) formula for maps with three boundaries that are not
necessarily tight. In fact, the ECF formula simply differs by some binomial
factors. As we will see in Section 6, the two formulas are equivalent, by a
canonical decomposition which consists in cutting a map with three arbitrary
boundaries along outermost minimal separating loops, resulting in three
annular maps and one tight pair of pants. However, our expression for
$T_{a,b,c}$ being even simpler than the ECF formula, it is desirable to have a
direct bijective proof of it, and this is the main objective of the present
paper.

Our results have interesting consequences for the statistics of large random
planar maps, which are explored in Section 6.3. There, for simplicity, we
restrict our attention to the case of quadrangulations. The aforementioned
canonical decomposition of a map with three boundaries into three annular maps
and a tight pair of pants allows one to define the exterior areas,
corresponding to the number of faces in the annular maps, the interior area,
corresponding to the number of faces in the tight pair of pants, and the
minimal separating cycle lengths, corresponding to the lengths of the three
boundaries of the tight pair of pants. In Theorem 34, we give a detailed limit
theorem for the joint law of these quantities in large quadrangulations with
three boundaries. We also provide an analogous statement for random annular
quadrangulations in Theorem 32, which relies on the results obtained in
[BG14].

Our strategy to prove Theorem 1 is the following. For $a=b=c=0$, the right-
hand side of (1) can be rewritten as $d\ln(R/t)/dt$ which, by results from
[BDFG04], is already known to be equal to the generating function $T_{0,0,0}$
of triply pointed bipartite maps (for completeness, we provide a slice-
theoretic rederivation of this fact in Appendix A). Then, we will exhibit a
bijection implying, as Corollary 5 below, that we have for any $a,b,c$

$T_{a,b,c}+t^{-1}\mathbf{1}_{a=b=c=0}=R^{a+b+c}\frac{X^{3}Y^{2}}{t^{6}}$ (3)

where $R$, $X$ and $Y$ are the generating functions of combinatorial objects
called respectively elementary slices, bigeodesic diangles, and bigeodesic
triangles (all these series are equal to $t$ when $g_{2},g_{4},\ldots$ all
vanish). These combinatorial objects will be defined in Section 2. The
notations are chosen to be consistent with those of [BG08, BG09a]: as we
discuss in Appendix B, bigeodesic diangles and triangles are the slice-
theoretic equivalents of objects appearing in the decomposition of well-
labeled maps (the slice interpretation of $R$ being already known). This makes
a connection with the bijective approach developed in [Mie09, AB13, BFG14].
Comparing (3) with the known expression for $T_{0,0,0}$, we get
$X^{3}Y^{2}/t^{6}=d\ln R/dt$ and Theorem 1 follows.

#### Outline.

Section 2 introduces the basic building blocks of our approach, namely tight
slices, bigeodesic diangles and bigeodesic triangles, and derives some
elementary enumeration results for those pieces. Section 3 explains how these
pieces can be assembled to produce a map with three tight boundaries. This
allows us to state our main bijective result, Theorem 4. To prove this
theorem, the difficult part is to decompose a map with three tight boundaries
back into basic building blocks. This decomposition takes place on the
universal cover of the map, which is a periodic infinite map which we describe
in Section 4. Section 5 then presents the decomposition of a map with three
tight boundaries, by first introducing the important geometric tool of
Busemann functions associated with infinite geodesics, and finishes the proof
of Theorem 4 by showing that this decomposition is indeed the inverse of the
assembling procedure. Section 6 discusses how to recover the ECF formula from
our results and a decomposition of pairs of pants into annular maps and tight
pairs of pants, and then states and proves our probabilistic applications on
the statistics of minimal separating cycles and areas in large random
quadrangulations with three boundaries. Concluding remarks and discussion on
future directions are gathered in Section 7. Finally, we recall in Appendix A
how to obtain the classical recursion relation (2) for slices, as well as the
reason why $d\ln(R/t)/dt$ is the generating function of triply pointed maps,
and in Appendix B we present another approach to bigeodesic diangles and
triangles in the case of quadrangulations, based on a bijection with labeled
trees.

#### Acknowledgements.

We thank Marie Albenque, Timothy Budd, Vincent Delecroix, Marco Mazzucchelli
and Bram Petri for valuable discussions. This project results from an
institutional collaboration between CEA and ENS de Lyon, and was initiated at
the occasion of the _Séminaire de combinatoire de Lyon à l’ENS_ which is
funded by the Labex Milyon (ANR-10-LABX-0070). The work of JB is partly
supported by the Agence Nationale de la Recherche via the grant
ANR-18-CE40-0033 “Dimers”.

##  2 Basic building blocks

In this section we introduce the fundamental building blocks of our approach.
We start with some preliminary definitions.

###  2.1 Preliminaries: geodesics and related concepts

In a map, a _geodesic_ between two vertices $v_{1}$ and $v_{2}$ is a path of
minimal length connecting them. This minimal length is by definition the
(graph) _distance_ $d(v_{1},v_{2})$ between the vertices $v_{1}$ and $v_{2}$.
Maps are assumed connected so geodesics between any two given vertices always
exist and $d(v_{1},v_{2})$ is a finite integer.

A _geodesic vertex_ between $v_{1}$ and $v_{2}$ is a vertex $v$ belonging to a
geodesic between them. Clearly, $v$ is a geodesic vertex if and only if

$d(v,v_{1})+d(v,v_{2})=d(v_{1},v_{2}).$ (4)

#### Bigeodesics.

In general, they may exist many geodesics between $v_{1}$ and $v_{2}$. But,
using the (local) planar structure of a map, it is often possible to single
out a canonical one. The previous works on slice decomposition were using the
notion of leftmost geodesic determined by the choice of an initial direction
at $v_{1}$. Here, we will need a related but slightly different notion, which
is that of leftmost bigeodesic determined by the choice of a geodesic vertex
between $v_{1}$ and $v_{2}$.

A _bigeodesic_ between two vertices $v_{1}$ and $v_{2}$ is a triple made of a
geodesic vertex $v$ between them and of two geodesics, one between $v$ and
$v_{1}$ and one between $v$ and $v_{2}$. Clearly the concatenation of these
two geodesics is a geodesic between $v_{1}$ and $v_{2}$, so that a bigeodesic
between $v_{1}$ and $v_{2}$ is entirely specified by the data of a geodesic
between $v_{1}$ and $v_{2}$ and of a vertex $v$ along this geodesic.

Viewing the bigeodesic as “launched” from the geodesic vertex $v$ towards
$v_{1}$ and $v_{2}$ respectively, we may introduce the notion of _leftmost
bigeodesic_ as follows. Assume that $d(v_{1},v_{2})\geq 2$ and that $v$ is
distinct from $v_{1}$ and $v_{2}$. We may partition the set of edges incident
to $v$ into three types:

  * (i)

those leading to a vertex strictly closer to $v_{1}$,

  * (ii)

those leading to a vertex strictly closer to $v_{2}$,

  * (iii)

those leading to a vertex that is neither strictly closer to $v_{1}$ nor to
$v_{2}$.

Ignoring the edges of type (iii), it is easily seen that, by planarity, there
exists an edge $e_{1}$ of type (i) and an edge $e_{2}$ of type (ii) such that,
when turning clockwise around $v$, all edges of type (i) appear between
$e_{1}$ and $e_{2}$ and all edges of type (ii) appear between $e_{2}$ and
$e_{1}$. We then consider the leftmost geodesic from $v$ to $v_{1}$ starting
with $e_{1}$, i.e. the geodesic whose first step goes along $e_{1}$ from $v$
to its neighbor at distance $d(v,v_{1})-1$ from $v_{1}$, and at each step,
goes along the leftmost edge (as viewed from the previous edge) among all
those going from the currently attained vertex to a vertex closer to $v_{1}$,
until $v_{1}$ is eventually reached. We similarly pick the leftmost geodesic
from $v$ to $v_{2}$ starting with $e_{2}$. Concatenating these two geodesics,
we obtain a bigeodesic between $v_{1}$ and $v_{2}$ launched from $v$, which is
by definition the leftmost bigeodesic we are looking for. Observe that the
leftmost bigeodesic is not well-defined if $v=v_{1}$ or $v=v_{2}$, and in
particular if $d(v_{1},v_{2})<2$.

#### Geodesic boundary intervals.

Consider a planar map with one boundary-face, which we denote $f_{0}$ and
which we choose as the external face in the planar representation of the map.
Let $c$ and $c^{\prime}$ be two corners incident to $f_{0}$. These corners
split the contour of $f_{0}$ in two portions, which we call _boundary
intervals_. When turning counterclockwise around the map (i.e., when walking
along the contour with $f_{0}$ on the right), the portion that starts at $c$
and ends at $c^{\prime}$ is denoted $[c,c^{\prime}]$. It forms a path on the
map, which may not be simple in general. In the particular case where it forms
a geodesic between the vertices incident to $c$ and $c^{\prime}$, then we say
that the boundary interval $[c,c^{\prime}]$ is _geodesic_ (the path is
necessarily simple in this case). Furthermore, if there exists no other
geodesic in the map with the same endpoints, then $[c,c^{\prime}]$ is said
_strictly geodesic_. In the figures, we will often use the graphical
convention of representing geodesic boundary intervals in blue, and strictly
geodesic boundary intervals in red.

###  2.2 Tight slices

Figure 3: Generic structure of a tight slice (the boundary-face is the outer
face). In this figure and the following, we represent geodesic boundary
intervals in blue and strictly geodesic ones in red. The corner
$c^{\prime\prime}$ is shown in blue since it is an intermediate corner on the
geodesic boundary interval $[c^{\prime},c]$. The width of the slice is the
length of $[c^{\prime},c^{\prime\prime}]$.

Our first building block is what we call a _tight slice_ , defined as a planar
bipartite map with one boundary-face having three distinguished (not
necessarily distinct) incident corners $c$, $c^{\prime}$ and
$c^{\prime\prime}$ appearing counterclockwise around the map such that:

  * $\scriptstyle{\circ}$

the boundary intervals $[c,c^{\prime}]$ and $[c^{\prime},c]$ are geodesic,

  * $\scriptstyle{\circ}$

the boundary interval $[c^{\prime\prime},c]$, called the _right boundary_ , is
strictly geodesic,

  * $\scriptstyle{\circ}$

the intervals $[c^{\prime\prime},c]$ and $[c,c^{\prime}]$ share only a common
vertex at $c$.

See Figure 3 for an illustration. Note that the constraints imply that
$[c^{\prime},c^{\prime\prime}]$ is also geodesic, and the length of this
interval is called the _width_ of the slice. The only tight slice of width
zero is equal to the _vertex-map_ , reduced to a single vertex and a single
face both of degree zero. Note that, if $c\neq c^{\prime\prime}$ (hence
$c^{\prime}\neq c^{\prime\prime}$), then $[c^{\prime},c]$ is nothing but the
leftmost bigeodesic launched from the vertex incident to $c^{\prime\prime}$
towards those incident to $c$ and $c^{\prime}$ respectively. A tight slice of
width $1$ is called an _elementary slice_.

######  Proposition 2.

The generating function of tight slices of width $\ell$, counted with a weight
$t$ per vertex not incident to the right boundary and a weight $g_{2k}$ per
inner face of degree $2k$ for all $k\geq 1$, is equal to $R^{\ell}$, with $R$
defined as in Theorem 1.

###### Proof.

It is known that $R$ counts elementary slices (for completeness, we provide a
proof in Appendix A). Given a tight slice of arbitrary width, let us consider
all the vertices incident to the boundary interval
$]c^{\prime},c^{\prime\prime}[$ (with endpoints excluded), and the leftmost
bigeodesics launched from them towards the vertices incident to $c^{\prime}$
and $c$. These bigeodesics necessarily follow the boundary towards
$c^{\prime}$, but may enter inside the map towards $c$. Cutting also these
bigeodesics splits the map into a $\ell$-tuple of elementary slices, and it is
straightforward to check that the decomposition is bijective. ∎

###  2.3 Bigeodesic diangles

Figure 4: Schematic picture of a bigeodesic diangle of nonnegative exceedance
$e$. The boundary intervals with the $\sim$ label have the same length and
meet only at $v_{1}$, and similarly for the $\approx$ label. The remaining two
other boundary intervals, of length $e$, may however share common vertices as
soon as $e>0$.

Our second building block is what we call a _bigeodesic diangle_ , or a
_diangle_ for short, which is again a planar bipartite map with one boundary-
face, with now four distinguished (not necessarily distinct) incident corners
$c_{1}$, $c_{12}$, $c_{2}$, $c_{21}$ appearing counterclockwise around the
map, and having the following properties:

  * $\scriptstyle{\circ}$

the boundary intervals $[c_{1},c_{2}]$ and $[c_{2},c_{1}]$ are geodesic,

  * $\scriptstyle{\circ}$

the boundary intervals $[c_{12},c_{2}]$ and $[c_{21},c_{1}]$ are strictly
geodesic,

  * $\scriptstyle{\circ}$

$[c_{21},c_{1}]$ and $[c_{1},c_{2}]$ share only a common vertex at the vertex
$v_{1}$ incident to $c_{1}$ and similarly, $[c_{12},c_{2}]$ and
$[c_{2},c_{1}]$ share only a common vertex at the vertex $v_{2}$ incident to
$c_{2}$.

See Figure 4 for an illustration. Note that the boundary intervals
$[c_{1},c_{12}]$ and $[c_{2},c_{21}]$ are necessarily geodesic. Let us denote
by $w_{12}$ and $w_{21}$ the vertices incident to $c_{12}$ and $c_{21}$. If
$w_{12}$ is different from $v_{1}$ and $v_{2}$, then $[c_{1},c_{2}]$ is the
leftmost bigeodesic launched from $w_{12}$ towards $v_{1}$ and $v_{2}$.
Similarly, if $w_{21}$ is different from $v_{1}$ and $v_{2}$, then
$[c_{2},c_{1}]$ is the leftmost bigeodesic launched from $w_{21}$. The corners
$c_{12}$ and $c_{21}$ (or the vertices $w_{12}$ and $w_{21}$ depending on the
context) will be referred to as the _attachment points_ of the diangle, for
reasons which will become clear in the next section.

The _exceedance_ $e$ of the diangle is defined as

$e=d(w_{12},v_{1})-d(w_{21},v_{1})=d(w_{21},v_{2})-d(w_{12},v_{2}).$ (5)

A diangle is said _balanced_ if its exceedance $e$ is $0$, that is if $w_{12}$
and $w_{21}$ are at the same distance from $v_{1}$, say. Note that the vertex-
map again satisfies all the required criteria for a balanced diangle. Apart
from this trivial case, any other balanced diangle has $d(v_{1},v_{2})\geq 2$,
with $w_{12}$ and $w_{21}$ different from $v_{1}$ and $v_{2}$ and from each
other, with $[c_{1},c_{2}]$ and $[c_{2},c_{1}]$ meeting only at $v_{1}$ and
$v_{2}$. This latter property is not necessarily true for unbalanced diangles,
as indicated in the caption of Figure 4.

We denote by $X$ the generating function of balanced bigeodesic diangles,
where the boundary-face and the vertices incident to the strictly geodesic
intervals $[c_{12},c_{2}]$ and $[c_{21},c_{1}]$ other than $w_{12}$ and
$w_{21}$ receive no weight. Note that the vertex-map contributes a weight $t$
to $X$.

Figure 5: The first terms in the expansion of $X$ for quadrangulations
($g_{2k}=g\,\delta_{k,2}$). The unfilled vertices (circles) receive no weight.

Even though we shall not need any precise expression for $X$, let us mention
that, by the results of [BG08], a very explicit formula can be given in the
case of quadrangulations ($g_{2k}=g\,\delta_{k,2}$), see equation (70) in
Appendix B. It yields the expansion
$X=t+gt^{2}+8g^{2}t^{3}+73g^{3}t^{4}+711g^{4}t^{5}+\ldots$, and the maps
corresponding to the first terms of this expansion are displayed in Figure 5.

With the same weighting convention as for balanced diangles, we have the
following property:

######  Proposition 3.

The generating function of bigeodesic diangles with nonnegative exceedance $e$
is equal to $R^{e}X$.

###### Proof.

Figure 6: Decomposition of a bigeodesic diangle of exceedance $e$ into a pair
made of a balanced bigeodesic diangle and a tight slice of width $e$.
Different situations occur according to which boundary is first hit by the
lefmost geodesic from $\overline{w}_{12}$ to $v_{2}$.

The property is obvious for $e=0$, so we may assume $e>0$. Let
$\overline{w}_{12}$ denote the vertex along $[c_{1},c_{2}]$ which is at the
same distance from $v_{1}$ as $w_{21}$. We have
$d(w_{12},\overline{w}_{12})=e$. Consider the leftmost bigeodesic launched
from $\overline{w}_{12}$ towards $v_{1}$ and $v_{2}$: its part towards $v_{1}$
follows the boundary, while its part towards $v_{2}$ may enter inside the
diangle. We denote by $\overline{v}_{2}$ the first vertex common to this part
and $[c_{2},c_{1}]$. Then, as illustrated in Figure 6, the bigeodesic splits
the map into two pieces. One of them is a balanced diangle with distinguished
corners incident to $v_{1}$, $\overline{w}_{12}$, $\overline{v}_{2}$ and
$w_{21}$, and the other is a tight slice of width $e>0$. The decomposition is
clearly a bijection and implies the wanted expression, by Proposition 2 (note
that the weight $t$ for $w_{12}$ must be transfered to $\overline{w}_{12}$ in
the tight slice). ∎

When all face weights are set to zero, $R^{e}X$ is equal to $t^{e+1}$, which
accounts for the diangle made of a chain of $e+1$ vertices and $e$ edges, with
$v_{1}=w_{21}$ at one extremity and $v_{2}=w_{12}$ at the other.

It is interesting to note that a tight slice of (positive) width $e$ is
nothing but a diangle of exceedance $e$ for which $c_{12}=c_{2}$ (with the
correspondance $c=c_{1}$, $c^{\prime}=c_{12}=c_{2}$,
$c^{\prime\prime}=c_{21}$). Note however that the weighting conventions differ
slightly (there is an extra weight $t$ for diangles).

We will not consider diangles with negative exceedance in this paper, since
their enumeration is more subtle.

###  2.4 Bigeodesic triangles

Figure 7: Schematic picture of a bigeodesic triangle. The vertices $w_{12}$,
$w_{23}$ and $w_{31}$ are colored in red to indicate that any geodesic from
$v_{1}$ to $v_{2}$ (respectively from $v_{2}$ to $v_{3}$, from $v_{3}$ to
$v_{1}$) must pass via $w_{12}$ (respectively $w_{23}$, $w_{31}$).

Our third and final building block is what we call a _bigeodesic triangle_ ,
or _triangle_ for short, which is again a planar bipartite map with one
boundary-face. It now has six distinguished incident corners $c_{1}$,
$c_{12}$, $c_{2}$, $c_{23}$, $c_{3}$, $c_{31}$ appearing counterclockwise
around the map, and having the following properties:

  * $\scriptstyle{\circ}$

the boundary intervals $[c_{1},c_{2}]$, $[c_{2},c_{3}]$ and $[c_{3},c_{1}]$
are geodesic, with no common vertex except at their endpoints $v_{1}$,
$v_{2}$, and $v_{3}$ (incident to $c_{1}$, $c_{2}$ and $c_{3}$, respectively),

  * $\scriptstyle{\circ}$

the boundary intervals $[c_{12},c_{2}]$, $[c_{23},c_{3}]$ and $[c_{31},c_{1}]$
are strictly geodesic,

  * $\scriptstyle{\circ}$

the boundary intervals $[c_{1},c_{12}]$ and $[c_{31},c_{1}]$ (respectively
$[c_{2},c_{23}]$ and $[c_{12},c_{2}]$, $[c_{3},c_{31}]$ and $[c_{23},c_{3}]$)
have the same length $s_{1}$ (respectively $s_{2}$, $s_{3}$).

  * $\scriptstyle{\circ}$

any geodesic from $v_{1}$ to $v_{2}$ (respectively from $v_{2}$ to $v_{3}$,
from $v_{3}$ to $v_{1}$) passes via $w_{12}$ (respectively $w_{23}$,
$w_{31}$), the vertex incident to $c_{12}$ (respectively $c_{23}$, $c_{31}$).

See Figure 7 for an illustration. Note that, if two corners among $c_{1}$,
$c_{12}$, $c_{2}$, $c_{23}$, $c_{3}$, $c_{31}$ are equal, then the above
properties imply that the triangle is reduced to the vertex-map. Note also
that the boundary intervals $[c_{1},c_{12}]$, $[c_{2},c_{23}]$ and
$[c_{3},c_{31}]$ are necessarily geodesic and that
$d(v_{1},v_{2})=s_{1}+s_{2}$, $d(v_{2},v_{3})=s_{2}+s_{3}$ and
$d(v_{3},v_{1})=s_{3}+s_{1}$. As in the case of diangles, the interval
$[c_{1},c_{2}]$ is the leftmost bigeodesic launched from $w_{12}$ towards
$v_{1}$ and $v_{2}$. Note also that a geodesic from $v_{1}$ to $v_{2}$, which
has to pass via $w_{12}$, necessarily sticks to $[c_{12},c_{2}]$ between
$w_{12}$ and $v_{2}$ since $[c_{12},c_{2}]$ is strictly geodesic. Similar
properties hold under cyclic permutations of the indices $1,2,3$. The corners
$c_{12},c_{23},c_{31}$ (or the vertices $w_{12},w_{23},w_{31}$ depending on
the context) will be referred to as the _attachment points_ of the triangle.

We call $Y$ the generating function of bigeodesic triangles, where the
boundary-face and the vertices incident to the strictly geodesic intervals
$[c_{12},c_{2}]$, $[c_{23},c_{3}]$ and $[c_{31},c_{1}]$ other than $w_{12}$,
$w_{23}$ and $w_{31}$ receive no weight. The vertex-map contributes a term $t$
to $Y$.

Figure 8: The first terms in the expansion of $Y$ for quadrangulations
($g_{2k}=g\,\delta_{k,2}$). The unfilled vertices (circles) receive no weight.

As was the case for the generating function $X$ of diangles, we shall not need
any precise expression for $Y$, even though the results of [BG08] provide an
explicit formula in the case of quadrangulations ($g_{2k}=g\,\delta_{k,2}$),
see again equation (70) in Appendix B. It yields the expansion
$Y=t+g^{3}t^{4}+21g^{4}t^{5}+324g^{5}t^{6}+\ldots$, and the maps corresponding
to the first terms of this expansion are displayed in Figure 8.

##  3 Assembling the building blocks

We now explain how to assemble a map with three tight boundaries from the
basic building blocks introduced in the previous section. We start from a
quintuple consisting of the following pieces:

  * $\scriptstyle{\circ}$

three bigeodesic diangles of nonnegative exceedances denoted by $e_{1}$,
$e_{2}$ and $e_{3}$,

  * $\scriptstyle{\circ}$

two bigeodesic triangles.

Recall that the boundaries of bigeodesic diangles and triangles are
conventionally colored in red and blue: a boundary edge is colored red if it
belongs to a boundary interval that is constrained to be strictly geodesic,
and is colored blue otherwise (i.e. it belongs to a geodesic boundary interval
which is not necessarily strictly geodesic). Generally speaking, the
assembling procedure consists in gluing the boundaries of the different pieces
together, a red edge being always glued to a blue edge. Some blue edges will
possibly remain unmatched and form the boundaries of the assembled map.

We shall discuss in fact two alternative assembling procedures, hereafter
numbered I and II, which are complementary in the sense that each of them
generates only a strict subset of the set of maps with three tight boundaries
but, taken together, they generate the full set.

Figure 9: The assembling procedure of type I. (a) We first identify the
attachment points of the two triangles and the three diangles as shown so as
to create a planar map with three special faces $F_{A}$, $F_{B}$ and $F_{C}$.
(b) The red-to-blue gluing around the special face $F_{A}$: the arrows
indicate the resulting identification between vertices (the identified
attachment points are shown in purple). Here, $e_{1}+e_{2}=2$ blue edges
remain unmatched. (c) Alternate representation of the gluing process: the
cyclic sequence of edges counterclockwise around $F_{A}$ may be coded by the
quasi-periodic lattice path with a unit up (respectively down) step for each
blue (respectively red) edge (the increments of the path are denoted
$\epsilon_{n}$ in the text). Each down (red) step is then matched to the next
up (blue) step on its right which returns to the same height. A number
$e_{1}+e_{2}$ of blue edges remain unmatched for each period
$\delta_{A}=\mathrm{deg}(F_{A})$. (d) Result of the gluing of $F_{A}$: we
obtain a boundary of length $e_{1}+e_{2}$ (the glued edges are represented by
dashed lines). The red-to-blue gluing of $F_{B}$ and $F_{C}$ is performed
similarly.

###  3.1 Description of the assembling procedures I and II

In a nutshell, the assembling procedures consist of two operations, which we
call _attachment_ and _red-to-blue gluing_. We start by describing these
operations in detail in the case of procedure I, then turn to procedure II
which only differs at the level of the attachment operation.

#### Procedure I.

Recall from Sections 2.3 and 2.4 that the attachment points of diangles and
triangles are the vertices from which their bigeodesic boundaries are
launched. The _attachment_ operation consists in identifying the attachment
points as shown on Figure 9(a). The resulting object is a planar map which, in
addition to the inner faces of the initial triangles and diangles, has three
extra _special_ faces, hereafter denoted $F_{A}$, $F_{B}$ and $F_{C}$. Each
special face is incident to four attachment points (after identification) and
its contour is made of alternating blue and red intervals, four of each color,
with an excess of blue edges ($e_{1}+e_{2}$ for $F_{A}$, $e_{2}+e_{3}$ for
$F_{B}$, $e_{3}+e_{1}$ for $F_{C}$).

The second operation is performed independently on each special face, and
consists in gluing all its incident red edges to blue edges so as to form a
face of smaller degree with only blue incident edges (thus the term  _red-to-
blue gluing_). More precisely, consider a special face, say $F_{A}$, and
follow its contour keeping the face on the left (i.e. we turn counterclockwise
around $F_{A}$, when it is represented as a bounded face in the plane): each
red edge immediately followed by a blue edge is glued to it, and we repeat the
process until no red edge is left. A convenient global description of this
operation can be given as follows: number the edges along the contour of
$F_{A}$ by integers, starting at an arbitrary position and in the same
direction as before. We set $\epsilon_{n}=1$ if the edge numbered $n$ is blue,
and $\epsilon_{n}=-1$ if it is red. The sequence $(\epsilon_{n})_{n}$ is
naturally defined for all $n\in\mathbb{Z}$ by periodicity, with a period
$\delta_{A}$ equal to the degree of $F_{A}$. Then, a red edge at position $k$
will be matched and glued to the blue edge at position $\ell$, where $\ell$ is
the smallest integer larger than $k$ such that
$\sum_{n=k}^{\ell}\epsilon_{n}=0$. Such $\ell$ necessarily exists since
$\epsilon_{k}=-1$ and $\sum_{n=k}^{k+\delta_{A}-1}\epsilon_{n}=e_{1}+e_{2}\geq
0$. See Figure 9 for an illustration. After the gluing step, a number
$e_{1}+e_{2}$ of blue edges remain unmatched. If $e_{1}+e_{2}>0$, these edges
form the contour of a boundary-face. If $e_{1}+e_{2}=0$, we instead obtain a
boundary-vertex, which corresponds to the vertex preceding any edge $k$ such
that $\sum_{n=k}^{\ell}\epsilon_{n}\leq 0$ for all $\ell\geq k$. Indeed, such
vertices corresponds to the maxima of the lattice path of Figure 9(c)—which is
periodic when $e_{1}+e_{2}=0$—and all of them are identified by gluing. All in
all, $F_{A}$ becomes a boundary of length $e_{1}+e_{2}$, and performing the
same operation on $F_{B}$ and $F_{C}$, these become boundaries of lengths
$e_{2}+e_{3}$ and $e_{3}+e_{1}$ respectively.

The assembling procedure is trivially adapted to the case where a triangle is
reduced to the vertex-map, by equipping its unique vertex with three
attachment points (dividing the surrounding corner in three sectors).
Similarly, when one of the exceedances is $0$ and the corresponding (balanced)
diangle is reduced to the vertex-map, we equip its unique vertex with two
attachment points. If $e_{1}=e_{2}=e_{3}=0$ and all the triangles/diangles are
reduced to the vertex-map, the object resulting from the assembling procedure
is the vertex-map itself. Besides this pathological case, we always obtain a
map in which the three boundaries are distinct elements of the map.

#### Procedure II.

Figure 10: The first step of the assembling procedure of type II, creating a
planar map with three special faces $F_{A}$, $F_{B}$ and $F_{C}$.

It differs from the previous one only by the identification between attachment
points, following now the prescription of Figure 10. The resulting object is
still a planar map with three special faces: two of them ($F_{A}$ and $F_{C}$)
are now incident to two attachment points (after identification) and the third
one ($F_{B}$) to eight attachment points. They all have a boundary made of
alternating blue and red intervals. We then repeat the red-to-blue gluing
operation described in the case I, creating three boundaries of respective
lengths $e_{2}$ (from $F_{A}$), $e_{3}$ (from $F_{C}$) and
$2e_{1}+e_{2}+e_{3}$ (from $F_{B}$). Again, the assembling procedure is
trivially extended to the case where some of the triangles/diangles are
reduced to the vertex-map, and the three boundaries are distinct as soon as at
least one of the building blocks is non trivial.

###  3.2 Properties of the assembling procedures

Let us first observe that, for both assembling procedures, the resulting map
is essentially bipartite: indeed its inner faces are those of the initial
triangles and diangles, with no modification of the degrees. The boundary
lengths are given by:

$\text{procedure I: }\begin{cases}2a=e_{1}+e_{2}\\\ 2b=e_{2}+e_{3}\\\
2c=e_{3}+e_{1}\end{cases}\qquad\text{procedure II: }\begin{cases}2a=e_{2}\\\
2b=2e_{1}+e_{2}+e_{3}\\\ 2c=e_{3}\end{cases}$ (6)

Here, $a$, $b$ and $c$ may either be integers or half-integers. They are all
integers (i.e., the map is bipartite) if $e_{1}$, $e_{2}$ and $e_{3}$ have the
same parity in case I, or if $e_{2}$ and $e_{3}$ are even in case II.
Otherwise, two of them are half-integers and the third is an integer, and the
map is quasi-bipartite.

We also see that, since $e_{1}$, $e_{2}$ and $e_{3}$ are assumed nonnegative,
we have the “triangle inequality” $b\leq c+a$ in case I, while we have $b\geq
c+a$ in case II (in both cases, we have $a\leq b+c$ and $c\leq a+b$). Upon
permuting $a$, $b$ and $c$ in case II, it is possible to obtain any possible
triple of boundary lengths in a bipartite or quasi-bipartite map with three
boundaries.

This suggests to introduce the following definition: a map with three
boundaries is said _of type I (respectively II)_ if the largest of the three
boundary lengths is smaller than or equal to (respectively larger than or
equal to) the sum of the two other boundary lengths. Clearly a map with three
boundaries is either of type I or type II, and may be both in the equality
case. We may now state the main bijective result of this paper.

######  Theorem 4.

For $e_{1}$, $e_{2}$ and $e_{3}$ fixed nonnegative integers, the assembling
procedure I (respectively II) is a bijection between the set of quintuples
made of two bigeodesic triangles and three bigeodesic diangles of nonnegative
exceedances $e_{1}$, $e_{2}$ and $e_{3}$, where at least one element differs
from the vertex-map, and the set of essentially bipartite planar maps with
three tight boundaries of type I (respectively II), where the lengths of the
boundaries are given by (6).

Figure 11: When the triangles and diangles have no inner faces, the assembling
procedures I and II generate maps corresponding to the generic cases I and II
of Figure 2.

It is instructive to examine the case where the triangles and diangles have no
inner faces: the triangles are then reduced to the vertex-map, while the
diangles are segments of lengths $e_{1}$, $e_{2}$ and $e_{3}$ (see Figure 11).
When these lengths are all positive, we recover precisely from the assembling
procedures I and II the two generic maps I and II displayed in Figure 2. The
degenerate cases correspond to having one or two lengths vanish, and the case
$e_{1}=e_{2}=e_{3}=0$ (all diangles reduced to the vertex-map) is pathological
when there are no inner faces.

To establish Theorem 4, two statements remain to be proved. First, we need to
show that the boundaries of the maps resulting from the assembling procedures
are indeed tight: this will be done in Section 4, see Proposition 9. Second,
we must check that both procedures are bijections: for this, we will exhibit
the inverse bijections in Section 5, see Propositions 23 and 25. Both proofs
are most conveniently performed by considering the universal cover of a map
with three boundaries, which we introduce in the next section. Before this,
let us explain why Theorem 4 implies Theorem 1, and also sketch the inverse of
procedure I in the simpler case of maps with three boundary-vertices
($e_{1}=e_{2}=e_{3}=0$).

###  3.3 Enumerative consequences

Recall that $T_{a,b,c}$ denotes the generating function of essentially
bipartite planar maps with three tight boundaries of lengths $2a$, $2b$, $2c$,
with the weighting convention of Theorem 1. As discussed in Section 1, this
theorem is implied by the following corollary of Theorem 4.

######  Corollary 5.

We have

$T_{a,b,c}=R^{a+b+c}\frac{X^{3}Y^{2}}{t^{6}}-t^{-1}\mathbf{1}_{a=b=c=0}$ (7)

where $X$ and $Y$ are the generating functions of bigeodesic balanced diangles
and triangles, respectively, as defined in Section 2.

###### Proof.

By Proposition 3, the generating function of quintuples made of two bigeodesic
triangles and three bigeodesic diangles of nonnegative exceedances $e_{1}$,
$e_{2}$ and $e_{3}$, is equal to $R^{e_{1}+e_{2}+e_{3}}X^{3}Y^{2}$. We exclude
the quintuple with all elements reduced to the vertex-map by substracting a
term $t^{5}\mathbf{1}_{e_{1}=e_{2}=e_{3}=0}$.

We then apply Theorem 4 and note that, by (6), we have
$e_{1}+e_{2}+e_{3}=a+b+c$ and
$\mathbf{1}_{e_{1}=e_{2}=e_{3}=0}=\mathbf{1}_{a=b=c=0}$ both in procedures I
and II. The claim then follows from the fact that the weight of a quintuple,
defined according to the conventions of Section 2, is equal to $t^{6}$ times
that of the corresponding map, defined as in Theorem 1. This is clear for face
weights since the inner faces are not modified by the bijection. For vertex
weights, the corrective factor $t^{6}$ comes from the identifications between
attachment points, see again Figures 9(a) and 10: there are generically twelve
attachment points in a quintuple, and they are identified in pairs so lead to
six vertices in the assembled map. We still obtain a difference of six in the
situations where some diangles or triangles are reduced to the vertex-map.
Note that the gluing between blue and red edges does not require corrective
factors, since by convention the vertices which are incident to red edges and
which are not attachment points receive no weight. In particular, potential
boundary-vertices are obtained from such unweighted vertices, as wanted. ∎

###  3.4 Disassembling a triply pointed map

We now sketch the proof of Theorem 4 in the case of procedure I with
$e_{1}=e_{2}=e_{3}=0$, which generates a triply pointed map (three boundary-
vertices). Boundary-vertices are always considered tight, so we only have to
exhibit the inverse bijection. The key point is to identify the attachment
points: once we know them, the decomposition into diangles and triangles is
done by cutting along leftmost bigeodesics.

Figure 12: Sketch of the decomposition of a triply pointed map, with marked
vertices $v_{A}$, $v_{B}$ and $v_{C}$. The set $S_{AB}$ consists of geodesic
vertices between $v_{A}$ and $v_{B}$ at distance $r_{A}$ from $v_{A}$. We pick
its extremal elements $v_{AB}$ and $v_{BA}$, from which the two leftmost
bigeodesics launched towards $v_{A}$ and $v_{B}$ delimit a maximal diangle
containing all other elements of $S_{AB}$, but not $v_{C}$. Similarly, we
construct two other disjoint diangles, formed by lefmost bigeodesics launched
from vertices $v_{BC}$ and $v_{CB}$, $v_{CA}$ and $v_{AC}$ respectively. The
complementary region consists of two geodesics triangles (one inside and one
outside).

Consider a planar bipartite map with three marked distinct vertices $v_{A}$,
$v_{B}$ and $v_{C}$ (as there are no boundary-faces, being essentially
bipartite is the same as being bipartite). Let us denote by $d_{AB}$, $d_{BC}$
and $d_{CA}$ their mutual distances. By the triangle inequalities and
bipartiteness, there exists three nonnegative integers $r_{A}$, $r_{B}$ and
$r_{C}$, at most one of them vanishing, such that

$d_{AB}=r_{A}+r_{B},\quad d_{BC}=r_{B}+r_{C},\quad d_{CA}=r_{C}+r_{A}.$ (8)

We then consider the set $S_{AB}$ of geodesic vertices between $v_{A}$ and
$v_{B}$ which are at distance $r_{A}$ from $v_{A}$ (hence distance $r_{B}$
from $v_{B}$). In the generic situation where $r_{A},r_{B},r_{C}$ are all
nonzero, we may single out canonically two “extremal” elements $v_{AB}$ and
$v_{BA}$ of $S_{AB}$ as follows. For $v$ and $v^{\prime}$ in $S_{AB}$,
consider the two leftmost bigeodesics towards $v_{A}$ and $v_{B}$ which are
launched from $v$ and $v^{\prime}$: these bigeodesics delimit two regions,
which turn out to be balanced bigeodesic diangles. Then, $v_{AB}$ and $v_{BA}$
are chosen in such a way that the diangle not containing $v_{C}$ is the
largest possible (and contains in particular all other elements of $S_{AB}$),
and such that $v_{A}$, $v_{AB}$, $v_{B}$ and $v_{BA}$ appears in clockwise
order around it. See Figure 12 for an illustration. We similarly define the
vertices $v_{BC}$, $v_{CB}$, $v_{CA}$ and $v_{AC}$. In this way, we obtain
three balanced bigeodesic diangles (the specific choice of $r_{A},r_{B},r_{C}$
ensures that these are disjoint), and the complementary region forms two
bigeodesic triangles, thereby giving the quintuple we are looking for. Note
that some diangles or triangles may be reduced to the vertex-map, for instance
it may happen that $v_{AB}=v_{BA}$ (resp. $v_{AB}=v_{BC}=v_{CA}$), in which
case the corresponding diangle (resp. triangle) is equal to the vertex-map.

In the situation where, say, $r_{C}$ vanishes, $v_{C}$ is actually an element
of $S_{AB}$: we simply cut the map along the leftmost bigeodesic launched from
$v_{C}$ towards $v_{A}$ and $v_{B}$, which transforms the map into a single
balanced bigeodesic diangle. This may be seen as a degeneration of the generic
situation, upon taking $v_{C}=v_{AB}=v_{BA}=v_{BC}=v_{CB}=v_{CA}=v_{AC}$, all
other elements of the quintuple being equal to the vertex-map.

This informal discussion overlooks some important details, such as the fact
that, in general, the leftmost bigeodesics merge before reaching $v_{A}$,
$v_{B}$ or $v_{C}$. We shall be more precise below when discussing the general
inverse bijection, which applies to both types of boundaries (vertices or
faces). Still, the core idea will be the same: upon defining in a suitable way
the distances $d_{AB},d_{BC},d_{CA}$ between the three boundaries, we will
define some parameters $r_{A},r_{B},r_{C}$ via the _equilibrium conditions_
(8), and we will then construct some _equilibrium vertices_ , analogous to the
vertices $v_{AB},v_{BA},v_{BC},v_{CB},v_{CA},v_{AC}$ defined above. Once these
equilibrium vertices are constructed, the decomposition is done by cutting
along leftmost bigeodesics. The main change induced by the presence of
boundary-faces is that all this construction must be performed on the
universal cover of the map, which we will define now.

##  4 The universal cover of a map with three boundaries

In this section we introduce the universal cover of a map with three
boundaries, which will be one of our main topological tools. Its construction
and some of its properties are discussed in Section 4.1. We explain in Section
4.2 how to visualize the assembling procedures directly on the universal
cover, before proving in Section 4.3 that the maps resulting from the
assembling procedures have tight boundaries.

###  4.1 Construction and properties of the universal cover

Let $M$ be a map with three boundaries
$\partial_{A},\partial_{B},\partial_{C}$, that are either boundary-faces or
boundary-vertices. We view $M$ as a graph embedded in a topological sphere
$S^{\prime}$, and we let $x_{A},x_{B},x_{C}$ be three distinguished points of
$S^{\prime}$, such that $x_{i}$ belongs to the $i$-th boundary component, that
is $x_{i}=\partial_{i}$ in the case of a boundary-vertex, or
$x_{i}\in\partial_{i}$ in the case of a boundary-face. We let $S$ be the
triply punctured sphere $S^{\prime}\setminus\\{x_{A},x_{B},x_{C}\\}$.

#### The universal cover of the triply punctured sphere.

The universal cover of the surface $S$ is the data of a simply connected
topological space $\tilde{S}$ and of a mapping $p:\tilde{S}\to S$ such that
for every $x\in S$, there is a neighborhood $U$ of $x$ in $S$ such that
$p^{-1}(U)$ is a disjoint union of open sets $U_{i}$, with
$p|_{U_{i}}:U_{i}\to U$ a homeomorphism. The pair $(\tilde{S},p)$ is unique up
to the natural notion of isomorphism.

Figure 13: A part of the universal cover of the triply punctured sphere. The
ideal corners
$\tilde{x}_{A},\tilde{x}_{B},\tilde{x}_{C},\tilde{x}_{B^{\prime}}$ correspond
respectively to the punctures $x_{A},x_{B},x_{C}$ and $x_{B}$ again.

It will be useful to consider the following concrete construction. Let $S_{0}$
denote the unit square with its four corners removed, and with its four sides
denoted by
$s_{\mathtt{a}},s_{\overline{\mathtt{a}}},s_{\mathtt{c}},s_{\overline{\mathtt{c}}}$
in counterclockwise direction. Note that the space obtained by gluing $S_{0}$
along its sides by identifying $s_{\mathtt{a}}$ with
$s_{\overline{\mathtt{a}}}$ and $s_{\mathtt{c}}$ with
$s_{\overline{\mathtt{c}}}$ (with a head to tail matching of their
orientations so that the resulting surface is orientable) is homeomorphic to
the triply punctured sphere $S$, and we let $p:S_{0}\to S$ be the resulting
projection.

Let $F=\langle\mathtt{a},\mathtt{c}\rangle$ be the free group with two
generators $\mathtt{a},\mathtt{c}$, that is the set of reduced finite words
$\mathtt{w}$ made of the four letters
$\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}$, where
$\overline{\mathtt{a}}=\mathtt{a}^{-1},\overline{\mathtt{c}}=\mathtt{c}^{-1}$
are the inverses of $\mathtt{a},\mathtt{c}$ (we thus let
$\overline{\overline{\mathtt{a}}}=\mathtt{a},\overline{\overline{\mathtt{c}}}=\mathtt{c}$).
Here, we say that a word is reduced if it does not contain an occurence of any
letter followed immediately by its inverse. The group operation is defined by
letting $\mathtt{v}\mathtt{w}$ be the reduced word obtained from the
concatenation of $\mathtt{v}$ and $\mathtt{w}$. The empty word $\varnothing$
is the neutral element of $F$. We identify $F$ with its Cayley graph with
generators
$\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$,
which is the infinite $4$-regular tree with root $\varnothing$, and we let
$|\mathtt{w}|$ be the length of the word $\mathtt{w}$, which is also its
distance in the tree to the root.

For every $\mathtt{w}\in F$, we let $S_{\mathtt{w}}$ be a copy of $S_{0}$,
that we can view as $\\{(x,\mathtt{w}):x\in S_{0}\\}$, with its four sides
denoted by
$s^{\mathtt{w}}_{\mathtt{a}},s^{\mathtt{w}}_{\overline{\mathtt{a}}},s^{\mathtt{w}}_{\mathtt{c}},s^{\mathtt{w}}_{\overline{\mathtt{c}}}$,
again oriented counterclockwise around $S_{\mathtt{w}}$. We consider the space
$\tilde{S}$ obtained by gluing the spaces $S_{\mathtt{w}}$ along their sides,
in such a way that $s^{\mathtt{w}}_{\mathtt{l}}$ is glued with
$s^{\mathtt{w}\mathtt{l}}_{\overline{\mathtt{l}}}$ for every letter
$\mathtt{l}\in\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$
(with a head to tail matching of their orientations). See Figure 13. We then
extend the projection $p$ to a mapping $p:\tilde{S}\to S$ by letting
$p(x,\mathtt{w})=p(x)$ for every $x\in S_{0}$ and $\mathtt{w}\in F$. This is
easily seen to be the universal cover of $S$.

The universal cover comes with its group of automorphisms $\mathrm{Aut}(p)$,
that are the homeomorphisms $u:\tilde{S}\to\tilde{S}$ such that $p\circ u=p$.
This group is isomorphic to the free group $F$ via the natural action of $F$
on $\tilde{S}$ defined by
$\mathtt{w}\cdot(x,\mathtt{v})=(x,\mathtt{w}\mathtt{v})$. Note that the
element of $\mathrm{Aut}(p)$ corresponding to $\mathtt{w}$ sends
$S_{\mathtt{v}}$ to $S_{\mathtt{w}\mathtt{v}}$, which may be arbitrarily far
apart. We denote by $A$ and $C$ the elements of $\mathrm{Aut}(p)$
corresponding to the action of $\mathtt{a}$ and $\mathtt{c}$ respectively. It
will be also convenient to introduce the automorphisms $B:=A^{-1}C^{-1}$ and
$B^{\prime}:=C^{-1}A^{-1}$ corresponding the respective actions of the
elements $\mathtt{b}:=\overline{\mathtt{a}}\,\overline{\mathtt{c}}$ and
$\mathtt{b}^{\prime}:=\overline{\mathtt{c}}\,\overline{\mathtt{a}}$ of $F$.

Classically, $\tilde{S}$ is a topological space homeomorphic to the open unit
disk. In fact, the universal cover of the triply punctured sphere can also be
constructed via hyperbolic geometry, see e.g. [Sti12, Section 5.3]. Figure 15
(left) displays the connection with our present construction: the gluing of
the squares $(S_{\mathtt{w}})_{\mathtt{w}\in F}$ can be realized as a regular
tiling in the hyperbolic plane made of ideal quadrangles.

For our purposes, it will be convenient to augment $\tilde{S}$ by adding back
the corners of the squares $S_{\mathtt{w}}$, and we denote the resulting space
by $\tilde{S}^{\prime}$. Note that, after gluing, a corner is common to
infinitely many squares: for instance, the corner denoted $\tilde{x}_{A}$ on
Figure 13 is common to all the squares $S_{\mathtt{a}^{n}}$ for
$n\in\mathbb{Z}$, similarly $\tilde{x}_{C}$ is common to all the
$S_{\mathtt{c}^{n}}$, while $\tilde{x}_{B}$ (resp. $\tilde{x}_{B^{\prime}}$)
is common to all the $S_{\mathtt{b}^{n}}$ and $S_{\mathtt{b}^{n}\mathtt{c}}$
(resp. $S_{(\mathtt{b}^{\prime})^{n}}$ and
$S_{(\mathtt{b}^{\prime})^{n}\mathtt{a}}$). The corners form a subset of the
‘ideal boundary’ of $\tilde{S}$ (which corresponds to the boundary of the disk
in Figure 15), and we therefore call them _ideal corners_. The projection
$p:\tilde{S}\to S$ extends to a continuous mapping111Note however that, if we
identify $\tilde{S}$ with the open unit disk as in Figure 15, then $p$ _does
not extend_ to a continuous function on the closed unit disk. It only admits
non-tangential limits at the ideal corners, which form a dense countable
subset of the unit circle. This is consistent with the topology of
$\tilde{S}^{\prime}$ resulting from the gluing of squares: in the hyperbolic
plane picture, given an ideal corner $\tilde{x}$, a neighborhood basis for
$\tilde{x}$ consists of the interiors of horocycles of center $\tilde{x}$.
from $\tilde{S}^{\prime}$ to the sphere $S^{\prime}$, and the group of
automorphisms $\mathrm{Aut}(p)$ acts naturally on $\tilde{S}^{\prime}$, each
ideal corner being left invariant by an infinite cyclic subgroup.

Finally, we recall that for any continuous path $\gamma:[0,1]\to S$ and any
$\tilde{\gamma}(0)\in p^{-1}(\gamma(0))$, there is a unique continuous path
$\tilde{\gamma}:[0,1]\to\tilde{S}$ starting at $\tilde{\gamma}(0)$ and such
that $p\circ\tilde{\gamma}=\gamma$. This path is called the _lift_ of $\gamma$
starting at $\tilde{\gamma}(0)$. The lift remains well-defined if the endpoint
$\gamma(1)$ is one of the punctures $x_{A},x_{B},x_{C}$, in that case
$\tilde{\gamma}(1)$ is an ideal corner. Lifting a path joining two punctures
may be done by splitting the path at an intermediate point, and choosing a
preimage for that point.

#### Lifting the map $M$ on the universal cover.

Figure 14: A part of the universal cover of a dumbbell-shaped map, having two
boundary-faces $\partial_{B}$ and $\partial_{C}$ and one boundary-vertex
$\partial_{A}=x_{A}$. We display in green the distinguished ideal vertex
$\tilde{\partial}_{A}=\tilde{x}_{A}$, and the contours (oriented
counterclockwise by convention) of the distinguished ideal faces
$\tilde{\partial}_{B}$, $\tilde{\partial}_{C}$ and
$\tilde{\partial}_{B^{\prime}}$. The embedding is good, according to the
definition given in Section 5.1.

Figure 15: Left: the regular tiling of the hyperbolic plane (here represented
in the Poincaré disk model) realizing the gluing of squares of Figure 13.
Right: the corresponding representation of the universal cover of the
dumbbell-shaped map of Figure 14. The green vertex at the ideal corner
$\tilde{x}_{A}$ has infinite degree. The contour of $\tilde{\partial}_{C}$
follows a horocycle with center the ideal corner $\tilde{x}_{C}$.

We now explain how the above considerations interact with the map $M$. By
viewing the (oriented) edges of $M$ as paths in $S^{\prime}$ parameterized by
$[0,1]$, we can consider the lifts of these edges in $\tilde{S}^{\prime}$,
which form an embedded graph $\tilde{M}$ in $\tilde{S}^{\prime}$.

The resulting embedded graph $\tilde{M}$ is an infinite map in the non-compact
surface $\tilde{S}^{\prime}$, with some faces or vertices of infinite degrees
(see Figure 14 and the right of Figure 15 for an example). More precisely,
$\tilde{M}$ has two possible types of vertices and faces: _regular_ vertices
and faces, which are the preimages of the non-boundary vertices and faces of
$M$ (keeping the same finite degree), and _ideal_ vertices and faces, which
have infinite degree, project to the boundaries of $M$, and are in bijection
with the ideal corners of $\tilde{S}^{\prime}$.

Let us provide some elements of justification to this dichotomy. First, since
$p:\tilde{S}\to S$ is a cover, it is immediate that a non-boundary vertex of
$M$, being placed at a point of $S$, lifts to vertices of $\tilde{M}$ with the
same finite degree. Next, if $f$ is a face of $M$ which is not a boundary-
face, then (at least when $f$ is not incident to a boundary-vertex, otherwise
we have to adapt slightly the argument) its contour $\partial f$ is homotopic
in $S$ to a point, so that its lifts form closed paths in $\tilde{S}$ bounding
the preimages of $f$ by $p$ (which therefore keep the same finite degree).
Now, if $f$ is a boundary-face of $M$, then its countour $\partial f$ is not
homotopic to a point, so that its preimages in $\tilde{S}$ are domains bounded
by lifts of $\partial f$, which form infinite paths of edges, resulting in
ideal faces with infinite degree. Finally, a boundary-vertex $v$ of $M$, being
placed at a puncture, lifts to an ideal corner $\tilde{x}$ of
$\tilde{S}^{\prime}$, and has infinite degree since $\tilde{x}$ is common to
infinitely many squares $S_{\mathtt{w}}$ contributing at least one edge
incident to $\tilde{x}$.

We call the infinite map $\tilde{M}$ the _universal cover_ of the map $M$. We
endow the set of its vertices $V(\tilde{M})$ with the graph distance
$\tilde{d}$, as for finite maps. The automorphism group of $\tilde{M}$ is the
same as that of $\tilde{S}$, $\mathrm{Aut}(p)$. It acts freely on the regular
vertices and faces, but each ideal vertex or face is left invariant by an
infinite cyclic subgroup, precisely the same as that fixing the corresponding
ideal corner of $\tilde{S}^{\prime}$. We point out that, in the concrete
construction of $\tilde{S}$ done above, it comes endowed with a distinguished
fundamental domain $S_{\varnothing}$, which in turn distinguishes four ideal
corners $\tilde{x}_{A}$, $\tilde{x}_{B}$, $\tilde{x}_{C}$ and
$\tilde{x}_{B^{\prime}}$ (see again Figure 13), and therefore four ideal
vertices or faces $\tilde{\partial}_{A}$, $\tilde{\partial}_{B}$,
$\tilde{\partial}_{C}$ and $\tilde{\partial}_{B^{\prime}}$ of $\tilde{M}$ (see
again Figure 14). We emphasize that this “rooting” results from our
construction of $\tilde{S}$ and _not_ from any extra data on $M$ other than
its distinguished boundaries.

Note that there is an important flexibility in our construction. Indeed, we
can choose in an arbitrary way the embedding of $M$ in $S$ or the projection
$p:S_{0}\to S$: the resulting $\tilde{S}$, $\tilde{M}$ and extension of $p$ to
$\tilde{S}$ will always be the same, up to isomorphisms. This observation will
be useful in Section 5.

Finally, we record the important observation that, if $M$ is essentially
bipartite, then its universal cover $\tilde{M}$ is bipartite. Indeed, every
simple cycle in $\tilde{M}$ is contractible and encloses a finite number of
faces of finite even degree, thus has even length.

###  4.2 Visualizing the assembling procedures on the universal cover

Figure 16: The partially assembled map $\mathcal{M}$ obtained from three
bigeodesic diangles and two bigeodesic triangles.

We now explain how the assembling procedures I and II can be visualized on the
universal cover of the triply punctured sphere. Let us start again from three
(bigeodesic) diangles and two triangles, as at the beginning of Section 3. In
the description given in Section 3.1, the assembling was done in two
successive operations, attachment then red-to-blue gluing. Here, it is
convenient to give an alternative (but equivalent) description in which the
assembling is done even more progressively, by doing first a partial
attachment and a partial red-to-blue gluing, thereby giving a _partially
assembled map_ , and then completing the assembling by another round of
attachment and red-to-blue gluing.

Precisely, the partially assembled map, which we denote by $\mathcal{M}$, is
constructed as displayed on Figure 16. Namely, we identify some of the
attachment points of the diangles and triangles together, but some of them,
denoted $u_{1}$, $u_{2}$, $u_{3}$ and $u_{4}$, remain unattached for now. Note
that the attachments that we perform are exactly those which are common to
procedures I and II, see again Figures 9(a) and 10. This results in a map with
one unique special face. We then perform red-to-blue gluing counterclockwise
around the special face (i.e. with this face on the left), with the important
prescription that we do not perform gluings which would require passing over
the attachment points $u_{1},\ldots,u_{4}$. For instance, a red edge preceding
the attachment point $u_{1}$ on the right triangle remains unglued, since it
would be glued with a blue edge beyond $u_{1}$. The partially assembled map
$\mathcal{M}$ is a planar bipartite map with one boundary-face and eight
distinguished incident corners: the attachment points
$u_{1},u_{2},u_{3},u_{4}$, at which we switch from blue to red when turning
counterclockwise around $\mathcal{M}$, and the corners
$u_{12},u_{23},u_{34},u_{41}$ at which we switch back from red to blue. In the
situation displayed on Figure 16, $u_{12}$ corresponds to a corner of the
right triangle, but it could also be, say, a corner of the middle diangle, if
the latter were longer. It is straightforward to check that $[u_{1},u_{12}]$
(resp. $[u_{41},u_{12}]$) is a strictly geodesic (resp. geodesic) boundary
interval of $\mathcal{M}$, as defined in Section 2.1, and similarly for the
other intervals around $\mathcal{M}$. Furthermore, by the definition of
exceedances, we see that

$\begin{split}d(u_{1},u_{12})+e_{1}+e_{2}&=d(u_{12},u_{2}),\\\
d(u_{2},u_{23})+e_{2}&=d(u_{23},u_{3}),\\\
d(u_{3},u_{34})+e_{1}+e_{3}&=d(u_{34},u_{4}),\\\
d(u_{4},u_{41})+e_{3}&=d(u_{41},u_{1}),\end{split}$ (9)

where $d$ denotes the graph distance in $\mathcal{M}$ and where, by a slight
abuse, we identify corners with their incident vertices. Note that the
boundary-face of $\mathcal{M}$ is not necessarily simple, as there may be
contacts between the different blue intervals (as said in the caption of
Figure 4, such contacts may exist in a diangle of positive exceedance, and may
subsist in the partial gluing, for instance if all the remaining pieces are
equal to the vertex-map).

In order to complete the assembling procedures, we have to identify the
remaining attachment points $u_{1},\ldots,u_{4}$ together: let
$\mathcal{M}_{\text{I}}$ (resp. $\mathcal{M}_{\text{II}}$) be the map obtained
from $\mathcal{M}$ by identifying $u_{1}$ with $u_{2}$ and $u_{3}$ with
$u_{4}$ (resp. $u_{1}$ with $u_{4}$ and $u_{2}$ with $u_{3}$). Note that these
identifications are exactly those which are specific to Figure 9(a) (resp.
Figure 10). In the terminology of Section 3.1, the maps
$\mathcal{M}_{\text{I}}$ and $\mathcal{M}_{\text{II}}$ have three “special”
faces, and we complete the assembling procedures by performing red-to-blue
gluing in each special face. It is straightforward to check that, for both
procedure I and procedure II, we obtain the same final result as with the
previous construction.

Figure 17: A visualization the assembling procedure I in the universal cover
of the triply punctured sphere. Inside each square $S_{\mathtt{w}}$ of the
tiling of Figure 13, we place a copy $\mathcal{M}_{\mathtt{w}}$ of the partial
gluing $\mathcal{M}$ of Figure 16. By attaching these maps together via their
attachment points as displayed with the arrows, and deforming appropriately to
perform the identification of vertices, we obtain the universal cover of the
map $\mathcal{M}_{\text{I}}$. To complete the assembling, we have to match and
glue the red and blue edges of the ideal faces together (some identification
between vertices are shown with dotted lines), thereby leaving only blue
unmatched edges incident to ideal faces. Procedure II works just the same,
except that we have to rotate each map $\mathcal{M}_{\mathtt{w}}$ by a
quarter-turn clockwise. We display in purple the path $\mathcal{G}$ and its
vertices $\tilde{x},A\tilde{x},A^{2}\tilde{x},\tilde{y},B\tilde{y}$, as
defined in Section 4.3 (in the displayed situation we have
$\Delta_{\mathtt{a}},\Delta_{\overline{\mathtt{c}}}>0$ but
$\Delta_{\overline{\mathtt{a}}}=0$). By Lemma 6, $\mathcal{G}$ is a geodesic
in $\tilde{M}$.

The interest of our alternative description is that it is now easier to
visualize the universal cover of the resulting assembled maps. Precisely, we
consider the square tiling $(S_{\mathtt{w}})_{\mathtt{w}\in F}$ of Section
4.1, and inside each square $S_{\mathtt{w}}$ we place a _copy_
$\mathcal{M}_{\mathtt{w}}$ of the partially assembled map $\mathcal{M}$. We
then identify the attachment points of these copies together as follows. In
the case of procedure I displayed on Figure 17, the attachment point
$u_{1}^{\mathtt{w}}$ of $\mathcal{M}_{\mathtt{w}}$ is identified with the
attachment point $u_{2}^{\mathtt{w}\mathtt{a}}$ of
$\mathcal{M}_{\mathtt{w}\mathtt{a}}$, and $u_{3}^{\mathtt{w}}$ is identified
with $u_{4}^{\mathtt{w}\mathtt{c}}$, for all $\mathtt{w}\in F$. Similarly, in
the case of procedure II, looking again at Figure 10, we see that the
attachment point $u_{2}^{\mathtt{w}}$ of $\mathcal{M}_{\mathtt{w}}$ is
identified with the attachment point $u_{3}^{\mathtt{w}\mathtt{a}}$ of
$\mathcal{M}_{\mathtt{w}\mathtt{a}}$, and $u_{4}^{\mathtt{w}}$ is identified
with $u_{1}^{\mathtt{w}\mathtt{c}}$. Of course, these identifications require
to deform the copies, and we can place the identified attachment vertices on
the sides of the squares if we want. At this stage, we obtain infinite maps
denoted by $\tilde{\mathcal{M}}_{\text{I}}$ and
$\tilde{\mathcal{M}}_{\text{II}}$, which are the respective universal covers
of $\mathcal{M}_{\text{I}}$ and $\mathcal{M}_{\text{II}}$, upon seeing their
three special faces as the three boundaries.

To complete the assembling procedure in the universal cover, we have to
perform a final round of red-to-blue gluing in each special (ideal) face. To
better understand how this works, it is useful to set up some notations. We
first introduce the shorthand notations

$I_{1}:=[u_{41},u_{12}],\quad I_{2}:=[u_{12},u_{23}],\quad
I_{3}:=[u_{23},u_{34}],\qquad I_{4}:=[u_{34},u_{41}]$ (10)

for the sides of $\mathcal{M}$ (so that $I_{j}$ is a bigeodesic launched from
the assembling point $u_{j}$). We also introduce the unified notations

$\text{procedure I: }\begin{cases}I_{\mathtt{a}}:=I_{1}\\\
I_{\overline{\mathtt{a}}}:=I_{2}\\\ I_{\mathtt{c}}:=I_{3}\\\
I_{\overline{\mathtt{c}}}:=I_{4}\end{cases}\qquad\text{procedure II:
}\begin{cases}I_{\mathtt{a}}:=I_{2}\\\ I_{\overline{\mathtt{a}}}:=I_{3}\\\
I_{\mathtt{c}}:=I_{4}\\\ I_{\overline{\mathtt{c}}}:=I_{1}\end{cases}$ (11)

and, for $\mathtt{w}\in F$ and
$\mathtt{l}\in\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$,
we let $I^{\mathtt{w}}_{\mathtt{l}}$ be the corresponding side of the copy
$\mathcal{M}_{\mathtt{w}}$. The interest of the unified notations is that the
attachment point of $I^{\mathtt{w}}_{\mathtt{l}}$ is identified with that of
$I^{\mathtt{w}{\mathtt{l}}}_{\overline{\mathtt{l}}}$, regardless of whether we
apply procedure I or II. As is apparent on (11), switching from procedure I to
procedure II amounts on the universal cover to rotating each
$\mathcal{M}_{\mathtt{w}}$ by a quarter-turn clockwise. Furthermore, the red
part of $I^{\mathtt{w}}_{\mathtt{l}}$ and the blue part of
$I^{\mathtt{w}{\mathtt{l}}}_{\overline{\mathtt{l}}}$ are incident to the same
special face, and appear successively counterclockwise around it. Thus, in the
red-to-blue gluing operation, the red edges in $I^{\mathtt{w}}_{\mathtt{l}}$
will first look for blue matches in
$I^{\mathtt{w}{\mathtt{l}}}_{\overline{\mathtt{l}}}$. Observe that, in all
this discussion, we can return from the universal cover to the sphere by
dropping the copy superscript.

Let us first consider the case $\mathtt{l}=\mathtt{a}$: by (9), we see that
the red part of $I_{\mathtt{a}}$ has $\Delta_{\mathtt{a}}$ fewer edges than
the blue part of $I_{\overline{\mathtt{a}}}$, with

$\text{procedure I:
}\quad\Delta_{\mathtt{a}}:=e_{1}+e_{2},\qquad\text{procedure II:
}\quad\Delta_{\mathtt{a}}:=e_{2}.$ (12)

Since $\Delta_{\mathtt{a}}$ is always nonnegative, when we complete the
assembling of $\mathcal{M}$, the red part of $I_{\mathtt{a}}$ is thus
completely glued to the beginning of the blue part of
$I_{\overline{\mathtt{a}}}$ (starting at the attachment point). If
$\Delta_{\mathtt{a}}>0$, there remains an unmatched blue part of length
$\Delta_{\mathtt{a}}$ which forms the contour of the boundary face
$\partial_{A}$; if $\Delta_{\mathtt{a}}=0$, $\partial_{A}$ is instead a
boundary-vertex as explained in Section 3.1. Translated in the universal
cover, the red part of $I_{\mathtt{a}}^{\mathtt{w}}$ is completely glued to
the beginning of the blue part of
$I_{\overline{\mathtt{a}}}^{\mathtt{w}\mathtt{a}}$ (starting at the attachment
point). If $\Delta_{\mathtt{a}}>0$, the remaining unmatched blue part of
$I_{\overline{\mathtt{a}}}^{\mathtt{w}\mathtt{a}}$ forms a lift of the contour
of the boundary face $\partial_{A}$; if $\Delta_{\mathtt{a}}=0$, we only get
an “exposed” blue vertex which we can place an ideal corner of
$\tilde{S}^{\prime}$ in order to form an ideal vertex of the map.

The case $\mathtt{l}=\mathtt{c}$ is entirely similar, the red part of
$I_{\mathtt{c}}$ having $\Delta_{\mathtt{c}}$ fewer edges than the blue part
of $I_{\overline{\mathtt{c}}}$, with

$\text{procedure I:
}\quad\Delta_{\mathtt{c}}:=e_{1}+e_{3},\qquad\text{procedure II:
}\quad\Delta_{\mathtt{c}}:=e_{3}.$ (13)

The cases $\mathtt{l}=\overline{\mathtt{a}}$ and
$\mathtt{l}=\overline{\mathtt{c}}$ are slightly more involved since they must
be considered altogether to construct the boundary $\partial_{B}$. Let
$\Delta_{\overline{\mathtt{a}}}$ (resp. $\Delta_{\overline{\mathtt{c}}}$) be
the difference between the length of the blue part of $I_{\mathtt{a}}$ (resp.
$I_{\mathtt{c}}$) and that of the red part of $I_{\overline{\mathtt{a}}}$
(resp. $I_{\overline{\mathtt{c}}}$). The relations (9) imply that
$\Delta_{\mathtt{b}}:=\Delta_{\overline{\mathtt{a}}}+\Delta_{\overline{\mathtt{c}}}$
is given by

$\text{procedure I:
}\quad\Delta_{\mathtt{b}}:=e_{2}+e_{3},\qquad\text{procedure II:
}\quad\Delta_{\mathtt{b}}:=2e_{1}+e_{2}+e_{3}$ (14)

and is therefore always nonnegative, but the signs of
$\Delta_{\overline{\mathtt{a}}}$ and $\Delta_{\overline{\mathtt{c}}}$
themselves are not fixed since they depend on the sizes of different diangles
and triangles. We therefore have three generic situations:

  * (i)

$\Delta_{\overline{\mathtt{a}}}$ and $\Delta_{\overline{\mathtt{c}}}$ are both
nonnegative,

  * (ii)

$\Delta_{\overline{\mathtt{a}}}$ is negative (hence
$\Delta_{\overline{\mathtt{c}}}$ is positive),

  * (iii)

$\Delta_{\overline{\mathtt{c}}}$ is negative (hence
$\Delta_{\overline{\mathtt{a}}}$ is positive).

Figure 18: The three generic situations corresponding to the possible signs of
$\Delta_{\overline{\mathtt{a}}}$ and $\Delta_{\overline{\mathtt{c}}}$: (i)
$\Delta_{\overline{\mathtt{a}}},\Delta_{\overline{\mathtt{c}}}\geq 0$, (ii)
$\Delta_{\overline{\mathtt{a}}}<0$ and $\Delta_{\overline{\mathtt{c}}}\geq 0$,
(iii) $\Delta_{\overline{\mathtt{a}}}\geq 0$ and
$\Delta_{\overline{\mathtt{c}}}<0$. In case (ii), some of the red edges of
$I_{\overline{\mathtt{a}}}^{\mathtt{a}}$ are matched to blue edges of
$I_{\mathtt{c}}^{\mathtt{a}\mathtt{b}}=I_{\mathtt{c}}^{\overline{\mathtt{c}}}$,
and similarly for case (iii) mutatis mutandis.

Let us discuss these three situations, illustrated on Figure 18. In the
situation (i), all the red edges of $I_{\overline{\mathtt{a}}}$ (resp.
$I_{\overline{\mathtt{c}}}$) are matched to blue edges of $I_{\mathtt{a}}$
(resp. $I_{\mathtt{c}}$. This implies two things about the universal cover,
one good and one bad. The good thing is that we only have “nearest neighbor”
gluings, as in the cases $\mathtt{l}=\mathtt{a},\mathtt{c}$ discussed before:
all the red edges of $I_{\overline{\mathtt{a}}}^{\mathtt{w}}$ (resp.
$I_{\overline{\mathtt{c}}}^{\mathtt{w}}$) are matched to blue edges of
$I_{\mathtt{a}}^{\mathtt{w}\overline{\mathtt{a}}}$ (resp.
$I_{\mathtt{c}}^{\mathtt{w}\overline{\mathtt{c}}}$). The bad thing is that,
since there are some unmatched blue edges in both $I_{\mathtt{a}}$ and
$I_{\mathtt{c}}$ (unless we are in the degenerate situation where
$\Delta_{\overline{\mathtt{a}}}$ or $\Delta_{\overline{\mathtt{c}}}$
vanishes), the lifts of the contour of $\partial_{B}$ do not remain in a
single copy $\mathcal{M}_{\mathtt{w}}$, but we have to consider two
neighboring copies, say $\mathcal{M}_{\mathtt{w}}$ and
$\mathcal{M}_{\mathtt{w}\overline{\mathtt{a}}}$, to obtain such a lift as the
concatenation of the unmatched blue parts of
$I_{\overline{\mathtt{a}}}^{\mathtt{w}}$ and
$I_{\overline{\mathtt{c}}}^{\mathtt{w}\overline{\mathtt{a}}}$.

In the situation (ii), some red edges of $I_{\overline{\mathtt{a}}}$ do not
find blue matches in $I_{\mathtt{a}}$, and therefore find them in
$I_{\mathtt{c}}$. This implies two things about the universal cover, one bad
and one good. The bad thing is that there are now “next nearest neighbor”
gluings in the universal cover, namely some red edges of
$I_{\overline{\mathtt{a}}}^{\mathtt{w}}$ are matched to blue edges of
$I_{\mathtt{c}}^{\mathtt{w}\mathtt{b}}$, where we recall that
$\mathtt{b}=\overline{\mathtt{a}}\,\overline{\mathtt{c}}$ is an element of
length $2$ in $F$. The good thing is, since all unmatched blue edges are found
on $I_{\mathtt{c}}$, the corresponding unmatched blue part of
$I_{\mathtt{c}}^{\mathtt{w}}$ forms a complete lift of the contour of
$\partial_{B}$ that remains in the single copy $\mathcal{M}_{\mathtt{w}}$.

The situation (iii) is entirely similar to the situation (ii), upon
interchanging the roles of $\mathtt{a}$ and $\mathtt{c}$, and therefore
changing $\mathtt{b}$ into
$\mathtt{b}^{\prime}=\overline{\mathtt{c}}\,\overline{\mathtt{a}}$.

###  4.3 Tightness of the boundaries resulting from the assembling procedures

We are now in position to prove that the maps resulting from the assembling
procedures have tight boundaries. Starting from three diangles and two
triangles, we denote by $\mathcal{M}$ the partially assembled map as defined
in the previous subsection, and by $M$ the completely assembled map (done
according to procedure I or II). As we have seen, the universal cover
$\tilde{M}$ of $M$ can be constructed directly by gluing infinitely many
copies of $\mathcal{M}$ along their boundaries.

A key ingredient in our proof is the path $\mathcal{G}$ displayed on Figure 17
and defined as follows. It consists of two parts which are both “launched”
from the attachment point between the copies $\mathcal{M}_{\varnothing}$ and
$\mathcal{M}_{\overline{\mathtt{a}}}$, and which go “towards” the ideal
corners $\tilde{x}_{A}$ and $\tilde{x}_{B}$, respectively, by following the
blue boundaries. More precisely, the part towards $\tilde{x}_{A}$ starts with
the blue part of $I_{\overline{\mathtt{a}}}^{\varnothing}$, then continues
with the unmatched blue part of $I_{\overline{\mathtt{a}}}^{\mathtt{a}}$, then
that of $I_{\overline{\mathtt{a}}}^{\mathtt{a}^{2}}$,
$I_{\overline{\mathtt{a}}}^{\mathtt{a}^{3}}$, etc. Let us denote by
$\tilde{x}$ the last vertex on the blue part of
$I_{\overline{\mathtt{a}}}^{\varnothing}$ which is glued to the red part of
$I_{\mathtt{a}}^{\overline{\mathtt{a}}}$. Then, our path passes through the
vertices $A^{n}\tilde{x}$ for all $n\geq 0$ (the unmatched blue part of
$I_{\overline{\mathtt{a}}}^{\mathtt{a}^{n}}$ going from $A^{n}\tilde{x}$ to
$A^{n+1}\tilde{x}$). In the case $\Delta_{\mathtt{a}}=0$, all the vertices
$A^{n}\tilde{x}$ are identified and placed at the ideal corner
$\tilde{x}_{A}$. In this case, $\tilde{x}_{A}$ is reached in a finite number
of steps by our path. As soon as $\Delta_{\mathtt{a}}$ is positive, our path
is infinite but, as visible on Figure 17, it still “tends” to $\tilde{x}_{A}$
in a sense, as it meets at $\tilde{x}$ the contour of the ideal face
containing $\tilde{x}_{A}$, and follows it counterclockwise onwards. The
description of the part towards $\tilde{x}_{B}$ is similar and just a bit more
involved, for the reasons discussed at the end of Section 4.2: assume for
instance that we are in case (i) with
$\Delta_{\overline{\mathtt{a}}},\Delta_{\overline{\mathtt{c}}}\geq 0$, then
the path with the blue part of $I_{\mathtt{a}}^{\overline{\mathtt{a}}}$,
continues with the unmatched blue part of $I_{\mathtt{c}}^{\mathtt{b}}$, then
that of $I_{\mathtt{a}}^{\mathtt{b}\overline{\mathtt{a}}}$,
$I_{\mathtt{c}}^{\mathtt{b}^{2}}$,
$I_{\mathtt{a}}^{\mathtt{b}^{2}\overline{\mathtt{a}}}$, etc. If
$\Delta_{\mathtt{b}}>0$, the path meets at a vertex denoted $\tilde{y}$ the
contour of the ideal face containing $\tilde{x}_{B}$, and follows it
counterclockwise onwards, passing in particular through $B^{n}\tilde{y}$ for
all $n\geq 0$. If $\Delta_{\mathtt{b}}=0$, the path reaches $\tilde{x}_{B}$ in
a finite number of steps, and we set $\tilde{y}:=\tilde{x}_{B}$. Then, the key
property of $\mathcal{G}$ is the following:

######  Lemma 6.

The path $\mathcal{G}$ is a geodesic in $\tilde{M}$.

###### Proof.

Intuitively, the reason is that, in Figure 17, we glue the copies along
(bi)geodesics. More formally, consider a path $\gamma$ in $\tilde{M}$ whose
two endpoints are on $\mathcal{G}$: we need to show that the length of
$\gamma$ is at least that of the portion of $\mathcal{G}$ having the same
endpoints. Our proof is by induction on the number of copies visited by
$\gamma$.

Precisely, we say that $\gamma$ _enters into $k$ copies_ if it can be written
as a concatenation of paths
$\gamma_{0}\gamma_{1}\ldots\gamma_{k}\gamma_{k+1}$, where $\gamma_{0}$ and
$\gamma_{k+1}$ are portions of $\mathcal{G}$ (which we do not include into the
copy count) and, for all $i=1,\ldots,k$, $\gamma_{i}$ is a path in the copy
$\mathcal{M}_{\mathtt{w}_{i}}$. Without loss of generality, we may assume that
the sequence $(\mathtt{w}_{i})_{i=1}^{k}$ is consistent with the structure of
gluings discussed at the end of Section 4.2, that is to say in the situation
(i) we have
$\mathtt{w}_{i+1}\mathtt{w}_{i}^{-1}\in\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$
for all $i=1,\ldots,k-1$ and, in the situations (ii) and (iii), we must also
allow the values $\mathtt{b},\overline{\mathtt{b}}$ and
$\mathtt{b}^{\prime},\overline{\mathtt{b}}^{\prime}$, respectively. Note that
ideal vertices lead to identifications between vertices belonging to distant
copies, but we can always assume that the $\mathtt{w}_{i}$ satisfy the above
constraint by considering that a long-range identification corresponds to a
concatenation of several paths $\gamma_{i}$ of length zero. We may also assume
that $\mathtt{w}_{1}$ and $\mathtt{w}_{k}$ are both of the form
$\mathtt{a}^{n}$, $\mathtt{b}^{n}$ or $\mathtt{b}^{n}\overline{\mathtt{a}}$
for some $n\geq 0$, as these correspond to the copies “carrying”
$\mathcal{G}$.

If $\gamma$ enters into $0$ copies, it is contained in $\mathcal{G}$ and we
are done. If it enters into $k\geq 1$ copies, we will show that we can modify
it, without increasing its length, so that it enters into at most $k-1$
copies. For this, we pick an $i$ such that $|\mathtt{w}_{i}|$ is maximal. Let
$\mathtt{l}\in\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$
be the last letter of $\mathtt{w}_{i}$, with the convention that
$\mathtt{l}=\mathtt{a}$ if $\mathtt{w}_{i}=\varnothing$. Then, from the
structure of gluings discussed above, from the definition of $\mathcal{G}$,
and from the maximality of $|\mathtt{w}_{i}|$, we see that $\gamma_{i}$ has
its two endpoints on the boundary interval
$I_{\overline{\mathtt{l}}}^{\mathtt{w}_{i}}$ which is geodesic in
$\mathcal{M}_{\mathtt{w}_{i}}$. Let $\gamma_{i}^{\prime}$ be the portion of
$I_{\overline{\mathtt{l}}}^{\mathtt{w}_{i}}$ with the same endpoints as
$\gamma_{i}$: $\gamma_{i}$ cannot be shorter than $\gamma^{\prime}_{i}$, so
$\gamma$ is not shorter than the path
$\gamma^{\prime}:=\gamma_{0}\ldots\gamma_{i-1}\gamma^{\prime}_{i}\gamma_{i+1}\ldots\gamma_{k+1}$.
We claim that $\gamma^{\prime}$ enters into (at most) $k-1$ copies. Indeed,
for $1<i<k$, $\gamma^{\prime}_{i}$ can be viewed as a path on the boundaries
of the copies $\mathcal{M}_{\mathtt{w}_{i-1}}$ and
$\mathcal{M}_{\mathtt{w}_{i+1}}$—which are necessarily the same in the
situation (i), but could differ in the situations (ii) and (iii)—so that we
may rewrite $\gamma_{i-1}\gamma^{\prime}_{i}\gamma_{i+1}$ as the concatenation
of (at most) two paths, each of them staying in one of these copies. The
argument is the same for $i=1$ or $i=k$, upon understanding that
$\mathcal{M}_{\mathtt{w}_{0}}$ and $\mathcal{M}_{\mathtt{w}_{k+1}}$ refer to
the path $\mathcal{G}$. ∎

######  Remark 7.

The projection of $\mathcal{G}$ on the finite map $M$ consists of a path
connecting the projection $x$ of $\tilde{x}$ to the projection $y$ of
$\tilde{y}$—this path is _not_ a geodesic in general— prolonged with
infinitely many turns around $\partial_{A}$ and $\partial_{B}$ when these are
boundary-faces.

We will need another technical lemma about $\mathcal{G}$ and its two
distinguished vertices $\tilde{x}$ and $\tilde{y}$:

######  Lemma 8.

Suppose that $\partial_{A}$ (resp. $\partial_{B}$) is a boundary-face of $M$,
and let $c$ be a cycle of $M$ freely homotopic in $S$ to the countour of
$\partial_{A}$ (resp. $\partial_{B}$), oriented counterclockwise. Then, $c$
can be lifted to a path $\tilde{c}$ in $\tilde{M}$ going from a vertex
$\tilde{z}$ to the vertex $A\tilde{z}$ (resp. $B\tilde{z}$), with $\tilde{z}$
belonging to $\mathcal{G}$ and situated between $\tilde{x}$ and $\tilde{y}$.

###### Proof.

If $\partial_{A}$ is a boundary-face, we denote its contour by
$\hat{\partial}_{A}$, which we orient counterclockwise and view as a loop
rooted at the projection $x$ of $\tilde{x}$ on $M$. If $c$ is freely homotopic
to $\hat{\partial}_{A}$, there exists a path $\gamma$ going from $x$ to a
point $z_{0}$ on $c$ such that $\gamma c\gamma^{-1}$ and $\hat{\partial}_{A}$
are homotopic as loops rooted at $x$. Lifting these loops to $\tilde{M}$, we
get paths with the same endpoints. Choosing the starting point to be
$\tilde{x}$, the final point must be $A\tilde{x}$ (since it is the final point
for the lift of $\hat{\partial}_{A}$), and we deduce that $\gamma
c\gamma^{-1}$ lifts to $\tilde{\gamma}\tilde{c}_{0}(A\tilde{\gamma})^{-1}$,
where $\tilde{\gamma}$ is the lift of $\gamma$ going from $\tilde{x}$ to a
vertex $\tilde{z}_{0}$, and $\tilde{c}_{0}$ is a lift of $c$ going from
$\tilde{z}_{0}$ to $A\tilde{z}_{0}$.

If $\tilde{z}_{0}$ lies on $\mathcal{G}$ we are done, otherwise we can tweak
it as follows. Note that the paths $A^{n}\tilde{c}_{0},n\in\mathbb{Z}$ are all
lifts of $c$, with the property that the endpoint of $A^{n}\tilde{c}_{0}$ is
the starting point of $A^{n+1}\tilde{c}_{0}$. The concatenation of these paths
is a doubly infinite path $\tilde{c}_{\infty}$ in $\tilde{M}$ (whose
projection to $M$ circles around $c$ indefinitely) which, by planarity,
necessarily crosses $\mathcal{G}$ at a vertex $\tilde{z}$ situated between
$\tilde{x}$ and $\tilde{y}$. Indeed, as visible on Figure 17, the portion of
$\mathcal{G}$ between $\tilde{x}$ and $\tilde{y}$ separates the copies
$\mathcal{M}_{\mathtt{w}}$ with a reduced word $\mathtt{w}$ starting with the
letter $\overline{\mathtt{a}}$, from the others. And, for $n\geq 0$ large
enough, $A^{-n}\tilde{z}_{0}$ will be in the former set of copies, and
$A^{n}\tilde{z}_{0}$ in the latter. The portion $\tilde{c}$ of
$\tilde{c}_{\infty}$ between $\tilde{z}$ and $A\tilde{z}$ is the wanted lift
of $c$.

The reasoning in the case where $\partial_{B}$ is a boundary-face and $c$ is a
cycle freely homotopic to its contour is entirely similar. ∎

######  Proposition 9.

The map $M$, assembled according to procedure I or II, has tight boundaries.

###### Proof.

Let us first prove that the boundary $\partial_{A}$ is tight. If it is a
boundary-vertex this is a tautology, otherwise it is a boundary-face of length
$\Delta_{\mathtt{a}}>0$, and we need to show that any cycle $c$ freely
homotopic to its contour has length at least $\Delta_{\mathtt{a}}$. Let us
lift $c$ to a path $\tilde{c}$ as in Lemma 8. Then, the length of $c$ is at
least $\tilde{d}(\tilde{z},A\tilde{z})$ which, by the triangle inequality,
satisfies

$\tilde{d}(\tilde{z},A\tilde{z})\geq\tilde{d}(\tilde{z},A\tilde{x})-\tilde{d}(A\tilde{x},A\tilde{z}).$
(15)

As $\mathcal{G}$ is a geodesic by Lemma 6, and as $\tilde{x}$ lies between
$\tilde{z}$ and $A\tilde{x}$ on $\mathcal{G}$, we have

$\tilde{d}(\tilde{z},A\tilde{x})=\tilde{d}(\tilde{z},\tilde{x})+\tilde{d}(\tilde{x},A\tilde{x})=\tilde{d}(\tilde{z},\tilde{x})+\Delta_{\mathtt{a}}.$
(16)

But we have $\tilde{d}(\tilde{z},\tilde{x})=\tilde{d}(A\tilde{x},A\tilde{z})$
since $A$ is an automorphism of $\tilde{M}$, hence

$\tilde{d}(\tilde{z},A\tilde{z})\geq\Delta_{\mathtt{a}}$ (17)

as wanted. The proof for $\partial_{B}$ is entirely similar, using again Lemma
8, and replacing in the above argument $\Delta_{\mathtt{a}}$ by
$\Delta_{\mathtt{b}}$, $A$ by $B$, and $\tilde{x}$ by $\tilde{y}$. Finally,
for $\partial_{C}$, we notice that throughout this section it plays a
symmetric role to $\partial_{A}$, viewing all the figures upside down (i.e.
rotated by $180$ degrees). ∎

To conclude this section, let us note that, symmetrically to the definition of
$\mathcal{G}$, we may define another geodesic $\mathcal{G}^{\prime}$ that
consists of two parts launched from the attachment point between the copies
$\mathcal{M}_{\varnothing}$ and $\mathcal{M}_{\overline{\mathtt{c}}}$ and
going towards the ideal corners $\tilde{x}_{C}$ and $\tilde{x}_{B^{\prime}}$,
respectively. Then, the copy $\mathcal{M}_{\varnothing}$ is delimited by the
four geodesics $\mathcal{G}$, $A\mathcal{G}$, $\mathcal{G}^{\prime}$ and
$C\mathcal{G}^{\prime}$, upon removing their pairwise common parts.
Furthermore, $A\mathcal{G}$ (resp. $C\mathcal{G}^{\prime}$) may be viewed as a
geodesic launched from the attachment point between
$\mathcal{M}_{\varnothing}$ and $\mathcal{M}_{\mathtt{a}}$ (resp.
$\mathcal{M}_{\mathtt{c}}$).

##  5 Decomposing a map with three tight boundaries

In this section we complete the proof of Theorem 4: starting from an
essentially bipartite planar map $M$ with three tight boundaries
$\partial_{A},\partial_{B},\partial_{C}$ of respective lengths $2a,2b,2c\geq
0$ on the triply punctured sphere $S$, we want to disassemble $M$ into two
bigeodesic triangles and three bigeodesic diangles with nonnegative
exceedances, in a way that inverts the assembling procedure.

We already sketched in Section 3.4 the decomposition in the case of triply
pointed maps ($a=b=c=0$). In order to generalize it to the case $a,b,c\geq 0$,
we have to find an analog of the equilibrium conditions (8), which involve the
distances $d_{AB},d_{BC},d_{CA}$ between the boundary-vertices. When some
boundaries are faces, we need appropriate analogs of these distances: it turns
out that such analogs may be constructed using so-called Busemann functions
defined on the universal cover $\tilde{M}$ of the map $M$. From this, we will
obtain the equilibrium vertices, from which we will launch leftmost
bigeodesics giving the decomposition we are looking for.

Our presentation is done in several steps. First, we discuss in Section 5.1
some graph-theoretical properties of the infinite map $\tilde{M}$, via the
notion of good embedding. Busemann functions, associated with infinite
geodesics, are then introduced in Section 5.2. We then explain in Section 5.3
how tight boundaries give rise to specific Busemann functions on $\tilde{M}$.
In Section 5.4, we adapt the notion of leftmost bigedeosic to $\tilde{M}$, and
use it to state the crucial diangle lemma. We construct equilibrium vertices
in Section 5.5, and use them to state the no less crucial triangle lemma. We
apply all these tools in Sections 5.6 and 5.7 to exhibit the inverses of the
assembling procedures I and II, respectively.

###  5.1 Graph-theoretical properties of the universal cover

Let us start by discussing some properties of the underlying graph of
$\tilde{M}$, which is infinite. For this, it is useful to introduce the notion
of “good embedding”.

Recall from Section 4.1 that the map $\tilde{M}$ is obtained by lifting the
map $M$ in the universal cover $\tilde{S}$ of the triply punctured sphere $S$,
and that we constructed $\tilde{S}$ as a square tiling
$(S_{\mathtt{w}})_{\mathtt{w}\in F}$ dual to the infinite $4$-regular tree
$F$. Let us denote by $\Sigma$ the projection of the boundaries of the square
$S_{\varnothing}$ (hence of any square $S_{\mathtt{w}}$) on the sphere
$S^{\prime}$: it is a path connecting $x_{A}$ to $x_{C}$ via $x_{B}$, see
again Figure 13.

In general, the edges of $\tilde{M}$ may connect vertices belonging to squares
arbitrarily far from each other in $F$, since the edges of $M$ may cross
$\Sigma$ in an arbitrarily complicated manner. We can simplify the situation
by an appropriate deformation of the embedding of $M$ in $S$ (hence, of the
embedding of $\tilde{M}$ in $\tilde{S}$). More precisely, we say that we have
a _good embedding_ if every edge of $M$, with its endpoints excluded, is
either entirely contained in $\Sigma$, or intersects it in at most one point.
Note that, in the latter case, the endpoints may also belong to $\Sigma$. See
again Figure 14 for an example.

######  Lemma 10.

Every map $M$ with three boundaries admits a good embedding.

###### Proof.

Consider the first derived map $M^{\prime}$ of $M$, which is defined [Tut63]
as the triangulation obtained by superimposing $M$ with its dual—which creates
a quadrangulation called the derived map [Sch15] of $M$—and splitting each
quadrangle into two triangles by connecting each vertex of $M$ to all
neighboring dual vertices. The vertex set of $M^{\prime}$ can be partitioned
into $\\{W,W^{*},W^{\dagger}\\}$, where $W$, $W^{*}$ and $W^{\dagger}$
correspond respectively to the vertices, faces and edges of $M$, and the edges
of $M^{\prime}$ correspond to the incidence relations in $M$. Note that the
vertices of $M^{\prime}$ have even degree, and those in $W^{\dagger}$ have
degree four.

The boundaries $\partial_{A},\partial_{B},\partial_{C}$ of $M$ become vertices
in $M^{\prime}$, which we can place at the punctures $x_{A},x_{B},x_{C}$ of
$S$. Let $P$ be a simple path on $M^{\prime}$ connecting $x_{A}$ to $x_{C}$
via $x_{B}$, and going “straight” at every vertex in $W^{\dagger}$. Such a
path always exists and, by deforming $M^{\prime}$ in such a way that $P$
coincides with $\Sigma$, we get a good embedding of $M$. ∎

When the embedding of $M$ is good, which we will assume from now on, the
lifted edges of $\tilde{M}$ remains “local” with respect to the tiling
$(S_{\mathtt{w}})_{\mathtt{w}\in F}$, i.e. they may only connect vertices
lying in the same square or in neighboring squares (i.e. squares
$S_{\mathtt{w}},S_{\mathtt{w}^{\prime}}$ with
$\mathtt{w}^{-1}\mathtt{w}^{\prime}\in\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$).
In particular, when we remove the finitely many vertices belonging to the
square $S_{\varnothing}$ (including those possibly placed on its boundaries
and at its ideal corners) and their incident edges, then $\tilde{M}$ is
disconnected in four infinite pieces. It follows that $\tilde{M}$ has
infinitely many ends in the graph-theoretical sense. These ends are in natural
bijection with those of the infinite $4$-regular tree $F$.

Recall that $\tilde{M}$ has two possible types of vertices, namely regular
vertices with finite degree, and ideal vertices (placed at ideal corners of
$\tilde{S}^{\prime}$) with infinite degree. In the absence of ideal vertices
(i.e. when $M$ has only boundary-faces), the underlying graph of $\tilde{M}$
is locally finite. In the presence of ideal vertices, we have the following
weaker property:

######  Lemma 11.

Let $v$ and $v^{\prime}$ be two vertices of $\tilde{M}$, and $r$ a nonnegative
integer. Then, the number of simple paths from $v$ to $v^{\prime}$ having
length at most $r$ is finite.

###### Proof.

Since we have a good embedding, we may keep track of the squares visited by a
path on $\tilde{M}$:

  * •

when following an edge between regular vertices, we may either remain in the
same square $S_{\mathtt{w}}$, or _move_ to a neighboring square
$S_{\mathtt{w}\mathtt{l}}$,
$\mathtt{l}\in\\{\mathtt{a},\overline{\mathtt{a}},\mathtt{c},\overline{\mathtt{c}}\\}$,

  * •

when passing through an ideal vertex projecting to $x_{A}$ (if there are any),
we may _jump_ from the square $S_{\mathtt{w}}$ to any square of the form
$S_{\mathtt{w}\mathtt{a}^{n}}$, with $n\in\mathbb{Z}$ arbitrary,

  * •

similarly, when passing through an ideal vertex projecting to $x_{C}$ (if
there are any), we may jump from $S_{\mathtt{w}}$ to any square
$S_{\mathtt{w}\mathtt{c}^{n}}$, $n\in\mathbb{Z}$,

  * •

finally, when passing through an ideal vertex projecting to $x_{B}$ (if there
are any), we may jump from $S_{\mathtt{w}}$ to squares of the form
$S_{\mathtt{w}\mathtt{b}^{n}}$, $S_{\mathtt{w}\mathtt{a}\mathtt{b}^{n}}$,
$S_{\mathtt{w}\mathtt{b}^{n}\mathtt{c}}$ or
$S_{\mathtt{w}\mathtt{a}\mathtt{b}^{n}\mathtt{c}}$, with $n\in\mathbb{Z}$ and
$\mathtt{b}=\overline{\mathtt{a}}\ \overline{\mathtt{c}}$ (see again Figure
13).

Without loss of generality, we may assume that the initial vertex $v$ belongs
to the square $S_{\varnothing}$. Then, we may reach after $r$ steps only
squares of the form
$S_{\mathtt{w}_{1}\mathtt{l}_{1}^{n_{1}}\cdots\mathtt{w}_{s}\mathtt{l}_{s}^{n_{s}}}$,
where $\mathtt{w}_{1},\ldots,\mathtt{w}_{s}$ are elements of $F$ such that
$|\mathtt{w}_{1}|+\cdots+|\mathtt{w}_{s}|+s\leq 2r$,
$\mathtt{l}_{1},\ldots,\mathtt{l}_{s}$ are equal to $\mathtt{a}$, $\mathtt{b}$
or $\mathtt{c}$, and $n_{1},\ldots,n_{s}$ are arbitrary integers. Hence,
generally speaking, infinitely many squares may be reached.

However, here we fix the endpoint $v^{\prime}$, hence the final square
$S_{\mathtt{w}_{1}\mathtt{l}_{1}^{n_{1}}\cdots\mathtt{w}_{s}\mathtt{l}_{s}^{n_{s}}}$.
We claim that, on any simple path from $v$ to $v^{\prime}$ with length at most
$r$, we may only visit squares of the form
$S_{\mathtt{v}_{1}\mathtt{l}_{1}^{m_{1}}\cdots\mathtt{v}_{s}\mathtt{l}_{s}^{m_{s}}}$,
where $\mathtt{v}_{1},\ldots,\mathtt{v}_{s}$ are elements of $F$ at bounded
distance from the neutral element $\varnothing$, and $m_{1},\ldots,m_{s}$ are
integers such that either $\lvert m_{i}\rvert\leq r$, or $\lvert
m_{i}-n_{i}\rvert\leq r$. The reason is that, if we perform a “big jump”
(larger than $r$) at an ideal vertex, then we cannot “undo” the jump in less
than $r$ steps since we cannot revisit the same ideal vertex again—here we use
the fact that $F$ is a free group, whose Cayley graph is a tree. Therefore,
the number of squares that may be visited is finite, and since each square
contains finitely many vertices, the claim follows. ∎

Note that Lemma 11 becomes false if, instead of simple paths, we consider
general paths, or even nonbacktracking paths. Indeed, without the simplicity
assumption, it is possible to do arbitrarily big jumps, then undo them.

Note also that we have not used the fact that the boundaries of $M$ are tight,
in fact all the discussion in this subsection remains valid without this
assumption.

###  5.2 Infinite geodesics and Busemann functions

Next, we introduce the main tool that will allow us to decompose maps with
tight boundary-faces. This tool is Busemann functions, a classical object of
metric geometry, see for instance Chapter 5 in [BBI01]. In the infinite map
$\tilde{M}$, we define an _infinite geodesic_ (also called a geodesic ray in
metric geometry) as an infinite sequence $(\gamma(t))_{t\in\mathbb{N}}$ of
vertices such that

$\tilde{d}(\gamma(t),\gamma(t^{\prime}))=\lvert t-t^{\prime}\rvert$ (18)

for all $t,t^{\prime}$ (recall that $\tilde{d}$ denotes the graph distance in
$\tilde{M}$). A _biinfinite geodesic_ is defined in exactly the same way,
except that the sequence is indexed by $\mathbb{Z}$ instead of $\mathbb{N}$.
To simplify our discussion, we overlook the fact that the map may be non
simple, which would in all rigor require to specify which edges are visited by
the geodesic.

With an infinite geodesic $\gamma$, we may associate its _Busemann function_
$B_{\gamma}$ which assigns to a vertex $v$ the quantity

$B_{\gamma}(v)=\lim_{t\to+\infty}\tilde{d}(v,\gamma(t))-t.$ (19)

This quantity is well-defined since the function
$t\mapsto\tilde{d}(v,\gamma(t))-t$ is nonincreasing, by virtue of the triangle
inequality, and bounded from below by $-\tilde{d}(v,\gamma(0))$. In fact,
since we are in a discrete metric space, we have
$B_{\gamma}(v)=\tilde{d}(v,\gamma(t))-t$ for $t$ large enough. We also have
$B_{\gamma}(\gamma(t))=-t$ for all $t$.

It is not difficult to check that $B_{\gamma}$ is a $1$-Lipschitz function,
changes parity along each edge since the map $\tilde{M}$ is bipartite, and
admits no local minimum: every vertex $v$ has an adjacent vertex $v^{\prime}$
such that $B_{\gamma}(v^{\prime})=B_{\gamma}(v)-1$.

For a biinfinite geodesic $\gamma$, we define its Busemann function
$B_{\gamma}$ in the same way. Note that a change of parametrization $t\mapsto
t+t_{0}$ of $\gamma$ changes $B_{\gamma}$ by a constant, so a Busemann
function should really be viewed as “defined modulo a constant”. Note however
that the change of parametrization $t\mapsto-t$ gives rise to a different
Busemann function.

######  Lemma 12.

Let $\gamma$, $\gamma^{\prime}$ be two infinite geodesics, and suppose that
there exists a finite set $V_{0}$ of vertices whose removal splits $\tilde{M}$
in several connected components, such that $\gamma$ and $\gamma^{\prime}$
eventually belong to different connected components (i.e. $\gamma(t)$ remains
in one connected component and $\gamma^{\prime}(t)$ in another for large
enough $t$). Then, the function $B_{\gamma}+B_{\gamma^{\prime}}$ admits a
global minimum, which is reached at some $v_{0}\in V_{0}$. Furthermore, there
exists at least one biinfinite geodesic along which $B_{\gamma}$ is strictly
increasing and $B_{\gamma^{\prime}}$ is strictly decreasing, and a vertex $v$,
not necessarily in $V_{0}$, belongs to such a geodesic if and only if it is a
global minimum of $B_{\gamma}+B_{\gamma^{\prime}}$.

###### Proof.

Let $v_{0}$ be a vertex at which $B_{\gamma}+B_{\gamma^{\prime}}$ attains its
minimum in the finite set $V_{0}$. For a given $v$, take $t$ large enough so
that $B_{\gamma}(v)=\tilde{d}(v,\gamma(t))-t$,
$B_{\gamma^{\prime}}(v)=\tilde{d}(v,\gamma^{\prime}(t))-t$, and so that
$\gamma(t)$ and $\gamma^{\prime}(t)$ are in different connected components
after removing $V_{0}$. By the triangle inequality, we have
$B_{\gamma}(v)+B_{\gamma^{\prime}}(v)\geq\tilde{d}(\gamma(t),\gamma^{\prime}(t))-2t$,
and we have
$\tilde{d}(\gamma(t),\gamma^{\prime}(t))=\tilde{d}(\gamma(t),v_{1})+\tilde{d}(v_{1},\gamma^{\prime}(t))$
for some $v_{1}\in V_{0}$ since a geodesic path from $\gamma(t)$ to
$\gamma^{\prime}(t)$ necessarily meets $V_{0}$ at some vertex $v_{1}$. We get

$B_{\gamma}(v)+B_{\gamma^{\prime}}(v)\geq(\tilde{d}(v_{1},\gamma(t))-t)+(\tilde{d}(v_{1},\gamma^{\prime}(t))-t)\geq
B_{\gamma}(v_{1})+B_{\gamma^{\prime}}(v_{1}),$ (20)

which is at least $B_{\gamma}(v_{0})+B_{\gamma^{\prime}}(v_{0})$. This proves
the first claim.

Consider now an arbitrary minimizer $v$ of $B_{\gamma}+B_{\gamma^{\prime}}$.
Since $B_{\gamma}$ has no local minimum, we can construct an infinite path
starting at $v$ along which $B_{\gamma}$ is strictly decreasing, and similarly
we can construct another infinite path starting at $v$ along which
$B_{\gamma^{\prime}}$ is strictly decreasing. It is straightforward to check
that, reversing the direction of the second path and concatenating it with the
first one, we get a biinfinite geodesic with the wanted property, and that
conversely any such geodesic can only pass through minimizers of
$B_{\gamma}+B_{\gamma^{\prime}}$. ∎

Note that, in this subsection, we have not used the fact that $\tilde{M}$ is
planar. In fact, our discussion (including Lemma 12) holds for an arbitrary
infinite graph.

###  5.3 Busemann functions associated with tight boundaries

We will now exploit the assumption that $M$ has tight boundaries. Consider a
boundary of $M$, say $\partial_{A}$ of length $2a$. As discussed in Section
4.1, $\partial_{A}$ has a distinguished lift $\tilde{\partial}_{A}$ which is
an ideal vertex if $a=0$, and an ideal face if $a>0$. In this latter case, we
let $\gamma_{A}$ be the biinfinite path on $\tilde{M}$ obtained by following
the contour of $\tilde{\partial}_{A}$ in the counterclockwise direction.
Choosing a reference point $\gamma_{A}(0)$ arbitrarily, $\gamma_{A}$ is
parametrized by $\mathbb{Z}$.

######  Lemma 13.

If $\partial_{A}$ is a tight boundary-face in $M$, then $\gamma_{A}$ is a
biinfinite geodesic in $\tilde{M}$.

###### Proof.

If we view the contour of $\partial_{A}$ as a biinfinite sequence of vertices
$(\lambda_{A}(t),t\in\mathbb{Z})$ obtained by cycling infinitely many times
around $\partial_{A}$, then [CdVE10, Proposition 2.5]—which is closely related
to the wrapping lemma of [BG14]—implies that any path of the form
$(\lambda_{A}(t+l),0\leq t\leq m)$ for $l\in\mathbb{Z}$ and $m\in\mathbb{N}$
is shortest in its homotopy class with fixed endpoints (such a path is called
‘tight’ in [CdVE10], so that our terminology agrees). Then, as noted in
[CdVE10, Section 2.1], this property is preserved by taking lifts in the
universal cover (and in fact, even in arbitrary covers). Since $\gamma_{A}$ is
one of these lifts, and since $\tilde{S}$ is simply connected, any two paths
between the same vertices in $\tilde{M}$ are homotopic, and we conclude that
$\gamma_{A}$ is a geodesic between any pair of points it visits, which is the
definition of a biinfinite geodesic. ∎

We may therefore define the function $\tilde{d}_{A}:V(\tilde{M})\to\mathbb{Z}$
as follows:

  * •

if $a=0$, then we let $\tilde{d}_{A}$ be the distance in $\tilde{M}$ to the
vertex $\tilde{x}_{A}$,

  * •

if $a>0$, then we let $\tilde{d}_{A}=B_{\gamma_{A}}$ be the Busemann function
associated with $\gamma_{A}$.

Let us record the relation

$\tilde{d}_{A}(Av)=\tilde{d}_{A}(v)-2a$ (21)

valid for any vertex $v$ of $\tilde{M}$, where $A\in\mathrm{Aut}(p)$ is the
automorphism defined in Section 4.1. This relation is immediate in the case
$a=0$; for $a>0$ it follows from the definition of the Busemann function
$B_{\gamma_{A}}$ and the fact that $A(\gamma_{A}(t))=\gamma_{A}(t+2a)$ for any
$t$.

In a completely similar manner, we define the functions $\tilde{d}_{B}$,
$\tilde{d}_{C}$ and $\tilde{d}_{B^{\prime}}$, which obey relations similar to
(21) mutatis mutandis. For later use, we record the following:

######  Lemma 14.

There exists a constant $k\in\mathbb{Z}$ such that, for any vertex $v$ of
$\tilde{M}$, we have

$\tilde{d}_{B^{\prime}}(Av)=\tilde{d}_{B}(v)+k$ (22)

and

$\tilde{d}_{B}(Cv)=\tilde{d}_{B^{\prime}}(v)-k+2b.$ (23)

###### Proof.

The first relation is a straightforward consequence of the fact that
$\tilde{\partial}_{B^{\prime}}=A\tilde{\partial}_{B}$. The constant $k$ is
equal to $0$ in the case $b=0$ while, for $b>0$, it satisfies
$A\gamma_{B}(k)=\gamma_{B^{\prime}}(0)$ (we could thus set it to $0$ too by
choosing the reference points on $\tilde{\partial}_{B}$ and
$\tilde{\partial}_{B^{\prime}}$ appropriately).

For the second relation, we note that
$\tilde{\partial}_{B}=C\tilde{\partial}_{B^{\prime}}$ hence there exists a
constant $k^{\prime}$ such that
$\tilde{d}_{B}(Cv)=\tilde{d}_{B^{\prime}}(v)+k^{\prime}$. But, by the relation
$B=A^{-1}C^{-1}$, we have

$\tilde{d}_{B}(v)=\tilde{d}_{B}(CABv)=\tilde{d}_{B^{\prime}}(ABv)+k^{\prime}=\tilde{d}_{B}(Bv)+k^{\prime}+k=\tilde{d}_{B}(v)+k^{\prime}+k-2b.$
(24)

hence $k^{\prime}=-k+2b$. ∎

######  Remark 15.

In this paper, we only consider the Busemann functions obtained by following
the contours of ideal faces counterclockwise. We surmise that considering the
clockwise orientation might be useful to study “strictly tight” boundaries,
i.e. boundaries whose contours are the unique paths of minimal length in their
homotopy class.

###  5.4 Leftmost bigeodesics and the diangle lemma

Throughout this section, we consider specifically the pair of ideal
vertices/faces $(\tilde{\partial}_{A},\tilde{\partial}_{B})$, but all the
discussion can be adapted to any other pair, e.g.
$(\tilde{\partial}_{A},\tilde{\partial}_{C})$,
$(\tilde{\partial}_{B},\tilde{\partial}_{B^{\prime}})$, etc. We start by
adapting the concepts of Section 2.1 to the context of the infinite map
$\tilde{M}$ and of Busemann functions.

#### Geodesics and bigeodesics.

A _geodesic towards $\tilde{\partial}_{A}$_ is a path on $\tilde{M}$ along
which $\tilde{d}_{A}$ is strictly decreasing, which stops at
$\tilde{\partial}_{A}$ if $a=0$, and which continues forever if $a>0$ (so that
$\tilde{d}_{A}$ tends to $-\infty$ along the path). Such a path $\gamma$ is
indeed a geodesic, i.e. satisfies
$\tilde{d}(\gamma(t),\gamma(t^{\prime}))=|t-t^{\prime}|$ for all
$t,t^{\prime}$ in its interval of definition. A geodesic towards
$\tilde{\partial}_{B}$ is defined similarly.

A _bigeodesic between $\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$_ is a
path which is both a geodesic towards $\tilde{\partial}_{A}$ in one direction,
and a geodesic towards $\tilde{\partial}_{B}$ in the other direction. Such
bigeodesics always exist: this is clear when $b=0$ (start at the vertex
$\tilde{\partial}_{B}$ and follow a path along which $\tilde{d}_{A}$
decreases) or similarly when $a=0$; when $ab>0$, we may invoke Lemma 12, with
$V_{0}$ the set of vertices lying in the square $S_{\varnothing}$ (given a
good embedding). We define the _distance $\tilde{d}_{AB}$ between
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$_ as

$\tilde{d}_{AB}:=\min_{v}\left(\tilde{d}_{A}(v)+\tilde{d}_{B}(v)\right).$ (25)

This denomination is consistent with the fact that, for $a=b=0$,
$\tilde{d}_{AB}$ is precisely the graph distance in $\tilde{M}$ between
$\tilde{x}_{A}$ and $\tilde{x}_{B}$. For $ab>0$, it is nothing but the minimal
value of the function $B_{\gamma_{A}}+B_{\gamma_{B}}$ as considered in Lemma
12.

In the Poincaré disk representation of $\tilde{S}$, a geodesic towards
$\tilde{\partial}_{A}$ forms a simple path which “ends” at the ideal point
$\tilde{x}_{A}$, see again Figure 15. A bigeodesic between, say,
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$, forms a simple path
connecting the ideal points $\tilde{x}_{A}$ and $\tilde{x}_{B}$. By planarity,
this path splits the disk (hence $\tilde{M}$) in two regions, which we may
distinguish as _left_ and _right_ , given an orientation of the bigeodesic
(say, from $\tilde{\partial}_{B}$ to $\tilde{\partial}_{A}$). Note that the
interiors of these regions may be disconnected, if the bigeodesic passes
through an ideal vertex on its way.

#### Geodesic vertices.

A _geodesic vertex between $\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$_
is a vertex belonging to a bigeodesic between $\tilde{\partial}_{A}$ and
$\tilde{\partial}_{B}$. It is straightforward to check (see again Lemma 12 in
the case $ab>0$) that $v$ is such a vertex if and only if

$\tilde{d}_{A}(v)+\tilde{d}_{B}(v)=\tilde{d}_{AB}.$ (26)

The quantity $\tilde{d}_{A}(v)$ is called the _$\tilde{d}_{A}$ -latitude_ of
the geodesic vertex $v$ between $\tilde{\partial}_{A}$ and
$\tilde{\partial}_{B}$.

######  Lemma 16.

For any $r\in\mathbb{Z}$, the set $I_{AB}(r)$ of geodesic vertices between
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$ having
$\tilde{d}_{A}$-latitude $r$ is finite.

###### Proof.

If $a=b=0$ then this is a corollary of Lemma 11. Suppose now that $a>0$. Given
a good embedding, any bigeodesic between $\tilde{\partial}_{A}$ and
$\tilde{\partial}_{B}$ must visit a vertex in the square $S_{\mathtt{a}^{n}}$,
for any $n\geq 0$. Let us denote by $r_{n}$ the maximal
$\tilde{d}_{A}$-latitude of a geodesic vertex belonging to
$S_{\mathtt{a}^{n}}$, then $r_{n+1}=r_{n}-2a<r_{n}$ by (21). Hence there
exists an $m$ such that $r_{m}<r$. If $b=0$, we see that any geodesic vertex
of $\tilde{d}_{A}$-latitude $r$ belongs to a geodesic (hence simple) path
between $\tilde{\partial}_{B}$ and a vertex of $S_{\mathtt{a}^{m}}$, so there
are finitely many of them by Lemma 11. If $b>0$, adapting the previous
reasoning shows that there exists an $\ell$ such that the minimal
$\tilde{d}_{A}$-latitude of a geodesic vertex in $S_{\mathtt{b}^{\ell}}$ is
larger than $r$. Therefore, any geodesic vertex of $\tilde{d}_{A}$-latitude
$r$ belongs to a geodesic (hence simple) path between a vertex of
$S_{\mathtt{a}^{m}}$ and a vertex of $S_{\mathtt{b}^{\ell}}$, and again there
are finitely many of them by Lemma 11. ∎

#### Leftmost bigeodesic via a geodesic vertex.

Given a geodesic vertex $v$ between $\tilde{\partial}_{A}$ and
$\tilde{\partial}_{B}$, we may, as in Section 2, “launch” from $v$ the
leftmost geodesics towards $\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$
(the planarity of $\tilde{M}$ is used to identify the first edges of these
leftmost geodesics, as in the finite case). The only potential difficulty is
that these geodesics may encounter ideal vertices of infinite degree. However,
by Lemma 16, only finitely many edges through a given ideal boundary point
make $\tilde{d}_{A}$ and $\tilde{d}_{B}$ decrease, therefore, when there are
any, there is always a leftmost one to be picked. Since $v$ is a geodesic
vertex, the concatenation of these two geodesics, oriented all the way from
$\tilde{\partial}_{B}$ to $\tilde{\partial}_{A}$, forms a bigeodesic between
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$ which we call the _leftmost
bigeodesic via $v$_ and denote $\mathcal{G}_{AB}(v)$. Note that the leftmost
geodesic towards $\tilde{\partial}_{A}$ eventually merges with it: this is
obvious for $a=0$ since the ideal vertex $\tilde{x}_{A}=\tilde{\partial}_{A}$
is reached in finitely many steps; for $a>0$, setting $\gamma_{A}$ as in
Section 5.3, then the leftmost geodesic from $v$ merges with $\gamma_{A}$ at
the vertex $\gamma_{A}(t)$ for the smallest value of $t$ such that
$\tilde{d}_{A}(v)=\tilde{d}(v,\gamma_{A}(t))-t$. Of course, a similar property
holds for the leftmost geodesic towards $\tilde{\partial}_{B}$.

#### The diangle lemma.

Figure 19: Illustration of the diangle lemma: we consider two geodesic
vertices $v$ and $v^{\prime}$ between $\tilde{\partial}_{A}$ and
$\tilde{\partial}_{B}$, such that $v^{\prime}$ lies on the right of the
leftmost bigeodesic $\mathcal{G}_{AB}(v)$ (shown in orange), and such that
$\tilde{d}_{A}(v)\geq\tilde{d}_{A}(v^{\prime})$. Then, $\mathcal{G}_{AB}(v)$
and $\mathcal{G}_{AB}(v^{\prime})$ (shown in purple) delimit a region
$\mathcal{D}_{AB}(v,v^{\prime})$ (shown in white) which is a bigeodesic
diangle of nonnegative exceedance
$\tilde{d}_{A}(v)-\tilde{d}_{A}(v^{\prime})$.

Consider two geodesic vertices $v$ and $v^{\prime}$ between
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$, such that $v^{\prime}$ lies
on the right of the leftmost bigeodesic $\mathcal{G}_{AB}(v)$ (oriented from
$\tilde{\partial}_{B}$ to $\tilde{\partial}_{A}$) or on it, and such that
$\tilde{d}_{A}(v)\geq\tilde{d}_{A}(v^{\prime})$. This situation is illustrated
on Figure 19.

We claim that the leftmost bigeodesic $\mathcal{G}_{AB}(v^{\prime})$ remains
on the right of $\mathcal{G}_{AB}(v)$. Indeed, as we start from $v^{\prime}$
and follow a geodesic towards $\tilde{\partial}_{A}$, it is not possible to
pass to the left of $\mathcal{G}_{AB}(v)$, since the latter consists of a
leftmost geodesic towards $\tilde{\partial}_{A}$ and we started on its right.
Furthermore, when we actually follow the leftmost geodesic from $v^{\prime}$
towards $\tilde{\partial}_{A}$, then we will eventually meet
$\mathcal{G}_{AB}(v)$ at a vertex $w$ (since all leftmost geodesics towards
$\tilde{\partial}_{A}$ eventually merge with it), and follow it onwards.
Similarly, as we start from $v^{\prime}$ and follow the leftmost geodesic
towards $\tilde{\partial}_{B}$, it is again not possible to pass to the left
of $\mathcal{G}_{AB}(v)$, hence $\mathcal{G}_{AB}(v^{\prime})$ stays to the
right of $\mathcal{G}_{AB}(v)$. In particular, $v$ lies on the left of
$\mathcal{G}_{AB}(v^{\prime})$, hence on the right of
$\mathcal{G}_{BA}(v^{\prime})$ (oriented from $\tilde{\partial}_{A}$ to
$\tilde{\partial}_{B}$). As we have
$\tilde{d}_{B}(v^{\prime})\geq\tilde{d}_{B}(v)$, we see that $v$ and
$v^{\prime}$ play a completely symmetric role, upon exchanging the roles of
$A$ and $B$ and viewing Figure 19 upside-down. We denote by $w^{\prime}$ the
vertex at which $\mathcal{G}_{AB}(v)$ and $\mathcal{G}_{AB}(v^{\prime})$ merge
when going towards $\tilde{\partial}_{B}$. Note that it is possible that
$\mathcal{G}_{AB}(v)$ and $\mathcal{G}_{AB}(v^{\prime})$ have intermediate
contacts at vertices of $\tilde{d}_{A}$-latitude strictly comprised between
$\tilde{d}_{A}(v^{\prime})$ and $\tilde{d}_{A}(v)$.

We now consider the closed region $\mathcal{D}_{AB}(v,v^{\prime})$ delimited
by $\mathcal{G}_{AB}(v)$ and $\mathcal{G}_{AB}(v^{\prime})$ (precisely, the
region which is on the right of $\mathcal{G}_{AB}(v)$ and on the left of
$\mathcal{G}_{AB}(v^{\prime})$, when orienting them from
$\tilde{\partial}_{B}$ to $\tilde{\partial}_{A}$), which we prune at $w$ and
$w^{\prime}$ to remove their (possibly infinite) common parts towards
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$. Note that
$\mathcal{D}_{AB}(v,v^{\prime})$ is connected but its interior may be
disconnected when there are intermediate contacts between
$\mathcal{G}_{AB}(v)$ and $\mathcal{G}_{AB}(v^{\prime})$. As a degenerate
case, it is possible to have
$\mathcal{G}_{AB}(v)=\mathcal{G}_{AB}(v^{\prime})$, and then
$\mathcal{D}_{AB}(v,v^{\prime})$ consists of a segment joining $v=w^{\prime}$
to $v^{\prime}=w$.

######  Lemma 17 (Diangle lemma).

$\mathcal{D}_{AB}(v,v^{\prime})$ is a bigeodesic diangle of nonnegative
exceedance $\tilde{d}_{A}(v)-\tilde{d}_{A}(v)$.

###### Proof.

We have to check that $\mathcal{D}_{AB}(v,v^{\prime})$ satisfies the axioms of
Section 2.3. First we observe that it is by construction a finite map with one
boundary-face (the interior of a closed cycle on $\tilde{M}$ always contains
finitely many vertices, edges and faces).

Then, to make the correspondence with the notations of Section 2.3, we take
$w_{12}=v$, $w_{21}=v^{\prime}$, $v_{1}=w$ and $v_{2}=w^{\prime}$ (see again
Figure 4) and the corners $c_{1},c_{12},c_{2},c_{21}$ are selected in a
natural manner. The boundary intervals $[c_{1},c_{2}]$ and $[c_{2},c_{1}]$ are
geodesic since they correspond to parts of the bigeodesics
$\mathcal{G}_{AB}(v)$ and $\mathcal{G}_{AB}(v^{\prime})$. The boundary
intervals $[c_{12},c_{2}]$ and $[c_{21},c_{1}]$ are strictly geodesic since
$\mathcal{G}_{AB}(v)$ and $\mathcal{G}_{AB}(v^{\prime})$ are actually
_leftmost_ bigeodesics: no geodesic between $v$ and $w^{\prime}$ can enter
into $\mathcal{D}_{AB}(v,v^{\prime})$, and similarly between $v^{\prime}$ and
$w$. Finally, $w$ (resp. $w^{\prime}$) is by definition the only vertex common
to $[c_{21},c_{1}]$ and $[c_{1},c_{2}]$ (resp. $[c_{12},c_{2}]$ and
$[c_{2},c_{1}]$). ∎

So far, our construction depends on the choice of geodesic vertices $v$ and
$v^{\prime}$ satisfying the aforementioned properties that $v^{\prime}$ is on
the right of $\mathcal{G}_{AB}(v)$ and that
$\tilde{d}_{A}(v)\geq\tilde{d}_{A}(v^{\prime})$. However, given two latitudes
$r\geq r^{\prime}$ such that the sets $I_{AB}(r)$ and $I_{AB}(r^{\prime})$, as
defined in Lemma 16, are both nonempty, there exists a canonical choice of
such vertices. Indeed, we may consider the _leftmost_ element $v$ of
$I_{AB}(r)$, defined as the only vertex $v\in I_{AB}(r)$ such that the region
on the left of $\mathcal{G}_{AB}(v)$ (again oriented from
$\tilde{\partial}_{B}$ to $\tilde{\partial}_{A}$) contains no other element of
$I_{AB}(r)$. Similarly, we choose $v^{\prime}$ to be the _rightmost_ element
of $I_{AB}(r^{\prime})$. Clearly $v^{\prime}$ is on the right of
$\mathcal{G}_{AB}(v)$, which actually passes through the leftmost element of
$I_{AB}(r^{\prime})$. This choice of $v$ and $v^{\prime}$ makes
$\mathcal{D}_{AB}(v,v^{\prime})$ the largest possible, as in the case of
triply pointed maps discussed in Section 3.4, and we will always encounter
such maximal diangles in the following.

###  5.5 Equilibrium vertices and the triangle lemma

In the previous subsection, we have only considered the pair
$(\tilde{\partial}_{A},\tilde{\partial}_{B})$. Let us now add
$\tilde{\partial}_{C}$ in the game: our purpose is to construct a bigeodesic
triangle $\mathcal{T}_{ABC}$ which, interestingly, is canonical in the sense
that it is entirely determined by the triplet of distinguished ideal corners
$(\tilde{x}_{A},\tilde{x}_{B},\tilde{x}_{C})$ of $\tilde{S^{\prime}}$. Indeed,
as discussed in Section 4.1, this triplet distinguishes the triplet
$(\tilde{\partial}_{A},\tilde{\partial}_{B},\tilde{\partial}_{C})$ of ideal
vertices/faces of $\tilde{M}$.

Recall the definition (25) of the distance $\tilde{d}_{AB}$ between
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$, and define $\tilde{d}_{BC}$
and $\tilde{d}_{CA}$ similarly. Inspired by the equilibrium conditions (8), we
define $r_{A}$, $r_{B}$ and $r_{C}$ by

$\tilde{d}_{AB}=r_{A}+r_{B},\quad\tilde{d}_{BC}=r_{B}+r_{C},\quad\tilde{d}_{CA}=r_{C}+r_{A}.$
(27)

Note that $r_{A}$, $r_{B}$ and $r_{C}$ may now be negative, since the
“renormalized” distances $\tilde{d}_{AB}$, $\tilde{d}_{BC}$ and
$\tilde{d}_{CA}$ may be negative in the presence of ideal faces. From the very
definition of Busemann functions and from the bipartiteness of $\tilde{M}$, we
get that the quantity $\tilde{d}_{A}(v)+\tilde{d}_{B}(v)$ has the same parity
for all $v$, which is also necessarily the parity of $\tilde{d}_{AB}$. We
immediately deduce that $\tilde{d}_{AB}+\tilde{d}_{BC}+\tilde{d}_{CA}$ is
even, hence $r_{A}$, $r_{B}$ and $r_{C}$ are integers.

We claim that the sets $I_{AB}(r_{A})$ (as defined in Lemma 16),
$I_{BC}(r_{B})$ and $I_{CA}(r_{C})$ are always nonempty: this is true when
$\tilde{\partial}_{A},\tilde{\partial}_{B},\tilde{\partial}_{C}$ are all ideal
faces, since the bigeodesics between them are infinite and therefore pass
through geodesic vertices of any latitude; this is also true when
$\tilde{\partial}_{A},\tilde{\partial}_{B},\tilde{\partial}_{C}$ are all ideal
vertices, as $I_{AB}(r_{A})$ projects to the set $S_{AB}$ considered in Figure
12 and similarly for the other sets; the other cases are left to the reader.

Furthermore, even though we had to choose a reference point along
$\tilde{\partial}_{A}$ to define the Busemann function $\tilde{d}_{A}$ when
$a>0$, and similarly for $\tilde{\partial}_{B}$ and $\tilde{\partial}_{C}$,
the sets $I_{AB}(r_{A})$, $I_{BC}(r_{B})$ and $I_{CA}(r_{C})$ _do not depend_
on these choices. Indeed, as we change the reference point along
$\tilde{\partial}_{A}$, say, $\tilde{d}_{A}$ is changed by a constant, but
$r_{A}$ gets changed by the same constant. We also have the identification
$I_{AB}(r_{A})=I_{BA}(r_{B})$.

We now define $v_{AB}$ to be the rightmost element of $I_{AB}(r_{A})$ (again
orienting from $\tilde{\partial}_{B}$ to $\tilde{\partial}_{A}$), and define
$v_{BC}$ and $v_{CA}$ similarly by permuting $A,B,C$ cyclically. We call
$v_{AB}$, $v_{BC}$ and $v_{CA}$ _equilibrium vertices_ , as they satisfy

$\begin{split}\tilde{d}_{A}(v_{AB})&=\tilde{d}_{A}(v_{CA})=r_{A},\\\
\tilde{d}_{B}(v_{AB})&=\tilde{d}_{B}(v_{BC})=r_{B},\\\
\tilde{d}_{C}(v_{BC})&=\tilde{d}_{C}(v_{CA})=r_{C}.\end{split}$ (28)

By the previous paragraph, the equilibrium vertices are intrinsic to
$\tilde{M}$.

Consider now the leftmost bigeodesics $\mathcal{G}_{AB}(v_{AB})$,
$\mathcal{G}_{BC}(v_{BC})$ and $\mathcal{G}_{CA}(v_{CA})$. We will show that
they delimit a region $\mathcal{T}_{ABC}$ which is a bigeodesic triangle. For
this, we first state some technical lemmas.

######  Lemma 18.

Let $v$ be a vertex strictly to the left of the leftmost bigeodesic
$\mathcal{G}_{AB}(v_{AB})$. Then, we have $\tilde{d}_{C}(v)>r_{C}$.

###### Proof.

Since $\tilde{x}_{C}$ is on the right of $\mathcal{G}_{AB}(v_{AB})$, any
geodesic from $v$ towards $\tilde{\partial}_{C}$ must cross
$\mathcal{G}_{AB}(v_{AB})$, at a vertex denoted $w$ such that
$\tilde{d}_{C}(v)>\tilde{d}_{C}(w)$. As $w$ is a geodesic vertex between
$\tilde{\partial}_{A}$ and $\tilde{\partial}_{B}$, we have
$\tilde{d}_{A}(w)+\tilde{d}_{B}(w)=\tilde{d}_{AB}=r_{A}+r_{B}$, and therefore
we have either $\tilde{d}_{A}(w)\leq r_{A}$ or $\tilde{d}_{B}(w)\leq r_{B}$.
In the former case, the definition of $\tilde{d}_{CA}$ implies that
$\tilde{d}_{C}(w)+\tilde{d}_{A}(w)\geq\tilde{d}_{CA}=r_{C}+r_{A}$ hence
$\tilde{d}_{C}(w)\geq r_{C}$. The same conclusion holds in the latter case,
using rather $\tilde{d}_{BC}$. ∎

######  Corollary 19.

Unless we have $v_{AB}=v_{BC}=v_{CA}$, the vertices $v_{BC}$ and $v_{CA}$ are
both strictly to the right of $\mathcal{G}_{AB}(v_{AB})$.

###### Proof.

Since $v_{BC}$ and $v_{CA}$ are both at $\tilde{d}_{C}$-latitude $r_{C}$, they
cannot be strictly on the left of $\mathcal{G}_{AB}(v_{AB})$ by the previous
lemma. If one of them, say $v_{BC}$, is on $\mathcal{G}_{AB}(v_{AB})$, then it
is equal to $v_{AB}$ since these two vertices are at the same
$\tilde{d}_{B}$-latitude $r_{B}$. But then, $v_{AB}=v_{BC}$ belongs to
$I_{CA}(r_{C})$, and is clearly the rightmost element $v_{CA}$ of that set. ∎

Reasoning as in the discussion of the diangle lemma, we deduce from Corollary
19 that $\mathcal{G}_{BC}(v_{BC})$ and $\mathcal{G}_{CA}(v_{CA})$ remain on
the right of $\mathcal{G}_{AB}(v_{AB})$. Furthermore, the two bigeodesics
$\mathcal{G}_{AB}(v_{AB})$ and $\mathcal{G}_{CA}(v_{CA})$ merge at a vertex
$v_{A}$ when following them towards $\tilde{\partial}_{A}$, but are disjoint
before. Similarly, we introduce the merging vertices $v_{B}$ and $v_{C}$ of
the bigeodesics going towards $\tilde{\partial}_{B}$ and
$\tilde{\partial}_{C}$, respectively.

We now consider the cycle on $\tilde{M}$ obtained by following