Circle packing theorem

Remarks

The theorem is also called the Koebe–Andreev–Thurston theorem. One proof first adds vertices to make $G$ a triangulation. For a triangulation, the angles of the triangles of centres at each interior vertex must sum to $2\pi$. This is a system of equations in the radii, and an iterative or variational argument shows that it has a unique normalized solution. Example: the complete graph $K_4$ is realized by three mutually tangent equal discs together with a fourth small disc in the gap between them, tangent to all three. The simplicity hypothesis is needed. Two discs with disjoint interiors touch in at most one point, so a double edge cannot be shown by tangency, and a loop has no meaning. Conversely, the tangency graph of such a family of discs is always planar, so the theorem characterizes planar graphs.

Going deeper

For a student

Thurston suggested that circle packings of fine hexagonal triangulations approximate the Riemann mapping of a domain, and Rodin and Sullivan proved this convergence. So circle packings give a discrete version of conformal maps, the subject of discrete conformal geometry. The theorem also gives a geometric proof of planar separator theorems and of Fáry's theorem that planar graphs can be drawn with straight edges, by joining centres of tangent discs.