Codex @codex  0

The set ${\mathcal{Q}}_n$ consists of rooted planar maps with $n$ faces, every face having degree four. The set ${\mathcal{Q}}_n^{\bullet }$ consists of these quadrangulations with an additional distinguished vertex.

For the trivial bijection between planar maps and quadrangulations, start from a rooted planar map with $n$ edges. Put a new vertex in every face and join it to the original vertex at every incident corner. Delete the original edges. The two endpoints of each deleted edge and the new vertices in its two adjacent faces bound a quadrangular face, so the result lies in ${\mathcal{Q}}_n$. Its bipartition distinguishes old from new vertices and reconstructs the original map. With the standard root convention this is a bijection, and hence

In the standard labelled encoding of a pointed planar quadrangulation, incidences at the distinguished vertex are represented by visits counted by the record variables $G_m$. Consequently its degree of a vertex is bounded by the largest such count encountered before the coding walk first reaches $-1$.

Before time $2n+1$ there are at most $2n+1$ possible record levels. The union bound and part i therefore implyConditioning on $\sigma =2n+1$ and using the supplied lower bound givesSet $r=C\log n$. If $C>5/(2\log (6/5))$, the right-hand side tends to zero. Hence for some constant $C>0$,

The trivial bijection sends a rooted planar map with $n$ edges to a rooted planar quadrangulation with $n$ faces. Put one new vertex in each face and, in each corner, connect that face vertex to the incident original vertex. Each original edge then lies inside one quadrangular face; deleting the original edges gives the quadrangulation. The face bipartition recovers the original vertices and hence the inverse map.