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

The trivial bijection between planar maps and quadrangulations sends a rooted planar map with $n\ge 1$ edges to a rooted planar map that is a planar quadrangulation with $n$ faces. Colour its original vertices black. Insert a white vertex in each face and connect it to every incident corner, keeping repeated incidences as separate edges. Erase the original edges. Each original edge now occupies one quadrangular face, even when its endpoints or incident faces coincide.

Fix the root convention by taking the first new outgoing edge clockwise after the original root edge at its origin. The resulting quadrangulation is a bipartite graph. Its vertex bipartition is recovered by colouring the root origin black and alternating colours along edges. Draw a black diagonal in every quadrangular face, then erase the white vertices and the quadrangulation edges. Root the recovered map at the first outgoing black diagonal counterclockwise after the quadrangulation root. These constructions are inverse.^[ref]

The bipartition is a partition of vertices, not of faces. It distinguishes the original vertices from the inserted face vertices and makes the inverse construction possible. The bijection transfers enumeration and random sampling questions between general planar maps and planar quadrangulations.