Circle packing theorem

The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A circle packing is a connected collection of circles (in general, on any Riemann surface) whose interiors are disjoint. The intersection graph of a circle packing is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. If the circle packing is on the plane, or, equivalently, on the sphere, then its intersection graph is called a coin graph; more generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. Coin graphs are always connected, simple, and planar. The circle packing theorem states that these are the only requirements for a graph to be a coin graph:

Circle packing theorem: For every finite connected simple planar graph G there is a circle packing in the plane whose intersection graph is (isomorphic to) G.

A maximal planar graph G is a finite simple planar graph to which no more edges can be added while preserving planarity. Such a graph always has a unique planar embedding, in which every face of the embedding (including the outer face) is a triangle. In other words, every maximal planar graph G is the 1-skeleton of a simplicial complex which is homeomorphic to the sphere. The circle packing theorem guarantees the existence of a circle packing with finitely many circles whose intersection graph is isomorphic to G. As the following theorem states more formally, every maximal planar graph can have at most one packing.

Koebe–Andreev–Thurston theorem: If G is a finite maximal planar graph, then the circle packing whose tangency graph is isomorphic to G is unique, up to Möbius transformations and reflections in lines.

Thurston observes that this uniqueness is a consequence of the Mostow rigidity theorem. To see this, let G be represented by a circle packing. Then the plane in which the circles are packed may be viewed as the boundary of a halfspace model for three-dimensional hyperbolic space; with this view, each circle is the boundary of a plane within the hyperbolic space. One can define a set of disjoint planes in this way from the circles of the packing, and a second set of disjoint planes defined by the circles that circumscribe each triangular gap between three of the circles in the packing. These two sets of planes meet at right angles, and form the generators of a reflection group whose fundamental domain can be viewed as a hyperbolic manifold. By Mostow rigidity, the hyperbolic structure of this domain is uniquely determined, up to isometry of the hyperbolic space; these isometries, when viewed in terms of their actions on the Euclidean plane on the boundary of the half-plane model, translate to Möbius transformations.

There is also a more elementary proof of the same uniqueness property, based on existence of a maximum value in any finite set and on the observation that, in the triangle connecting the centers of three mutually tangent circles, the angle formed at the center of one of the circles is monotone decreasing in its radius and monotone increasing in the two other radii. Given two packings for the same graph ${\displaystyle G}$, one may apply reflections and Möbius transformations to make the outer circles in these two packings correspond to each other and have the same radii. Then, let ${\displaystyle v}$ be an interior vertex of ${\displaystyle G}$ for which the circles in the two packings have sizes that are as far apart as possible: that is, choose ${\displaystyle v}$ to maximize the ratio ${\displaystyle r_{1}/r_{2}}$ of the radii of its circles in the two packings. For each triangular face of ${\displaystyle G}$ containing ${\displaystyle v}$, it follows that the angle at the center of the circle for ${\displaystyle v}$ in the first packing is less than or equal to the angle in the second packing, with equality possible only when the other two circles forming the triangle have the same ratio ${\displaystyle r_{1}/r_{2}}$ of radii in the two packings. But the sum of the angles of all of these triangles surrounding the center of the triangle must be ${\displaystyle 2\pi }$ in both packings, so all neighboring vertices to ${\displaystyle v}$ must have the same ratio as ${\displaystyle v}$ itself. By applying the same argument to these other circles in turn, it follows that all circles in both packings have the same ratio. But the outer circles have been transformed to have ratio one, so ${\displaystyle r_{1}/r_{2}=1}$ and the two packings have identical radii for all circles.

A conformal map between two open sets in the plane or in a higher-dimensional space is a continuous function from one set to the other that preserves the angles between any two curves. The Riemann mapping theorem, formulated by Bernhard Riemann in 1851, states that, for any two open topological disks in the plane, there is a conformal map from one disk to the other. Conformal mappings have applications in mesh generation, map projection, and other areas. However, it is not always easy to construct a conformal mapping between two given domains in an explicit way.

At the Bieberbach conference in 1985, William Thurston conjectured that circle packings could be used to approximate conformal mappings. More precisely, Thurston used circle packings to find a conformal mapping from an arbitrary open disk A to the interior of a circle; the mapping from one topological disk A to another disk B could then be found by composing the map from A to a circle with the inverse of the map from B to a circle.