Planar map

A planar map is a connected graph that is a planar graph together with a fixed embedding in the sphere, considered up to orientation-preserving homeomorphism. A rooted planar map has a distinguished oriented edge, which removes most embedding symmetries.

A random planar map is a planar map sampled from a specified probability distribution. A common finite model chooses uniformly among rooted maps with $n$ edges, where a root is a distinguished oriented edge. Sampling maps means sampling embeddings as well as abstract graphs; distinct cyclic arrangements of edges can describe different maps.^[ref]

For a connected map on the sphere, the Euler formula for a connected planar graph gives $V-E+F=2$. Thus conditioning on $E=n$ fixes $V+F=n+2$ but permits random numbers of vertices and faces. One may instead restrict every face to degree three or four, giving random triangulations or quadrangulations. These are different probability models and need not yield the same finite-size statistics. Distances in large random maps motivate probabilistic models of random geometry.

A face of a planar map is a connected component of the complement of its embedded graph. Its degree is the number of edge incidences around its boundary, counted with multiplicity, and the sum of all face degrees is twice the number of edges.

A rooted planar map is a planar map with a distinguished oriented edge called its root edge. Its tail is the root vertex, and the face on a chosen side of the edge may be designated as the root face.

A planar quadrangulation is a planar map in which every face has degree four, with incidences counted with multiplicity. A pointed quadrangulation additionally has a distinguished vertex.

A squaregraph has separate conditions on bounded faces and interior vertex degrees; its outer face need not be quadrilateral.

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.