Jérémie Bettinelli École polytechnique Laboratoire d'informatique (LIX) 91128 Palaiseau Cedex FRANCE E-mail: firstname « . » lastname « at » normalesup « . » org Office: 2023 Phone: (+33) (0)1 77 57 80 61

Désolé, pas de version française

Sketchfab folder

We now look at quadrangulations of more general surfaces. The first natural generalization is to consider the case of the disk. More precisely, a plane quadrangulation with a boundary is a plane map of the sphere where all the faces except one (the external face) are incident to 4 half-edges. The external face should be thought of as a hole in the sphere and it is not represented on the figures (only its boundary is visible). Note also that this boundary is not necessary (and actually very unlikely to be) a simple curve, so that, although the surface is very close to a disk, it is not exactly one. However, we may show that, in the limit for the proper scaling, when the length of the boundary is of order the square root of the number of faces, the object that arises is a topological disk. In contrast, when the length of the boundary grows faster than the square root of the number of faces, we obtain a Brownian tree in the limit, that is, the same object as for a uniform tree. This can be intuited from the following simulations.

Cactus embedding

Here, we may also look at the cactus embedding of these plane quadrangulations with a boundary. The boundary is outlined in red.

	n = 10 000 and p = 100	n = 10 000 and p = 1 000

Slice decomposition

The slice decomposition follows from an idea of Bouttier and Guitter. We still consider plane quadrangulations with a boundary and we represent the slices by different (random) colors. The slices are defined as follows. First, pick a vertex uniformly at random in the map. Then, for every vertex on the boundary, consider the left-most geodesic in the map starting from this vertex and ending at the vertex you picked. The slices are the pieces of the map that are delimited by these geodesics.