The circle packing theorem (also known as the Koebe–Andreev–Thurston theorem) describes the possible patterns of tangent circles among non-overlapping circles in the plane. A circle packing is a collection of circles whose union is connected and whose interiors are disjoint. The intersection graph of a circle packing, called a coin graph, is the graph having a vertex for each circle, and an edge for every pair of circles that are tangent. 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: every finite connected simple planar graph has a circle packing in the plane whose intersection graph is isomorphic to .
A stronger form of the circle packing theorem applies to any polyhedral graph and its dual graph, and proves the existence of a primal–dual packing, circle packings for both graphs that cross at right angles. Circle packings and their tangencies, and the circle packing theorem, have been extended to arbitrary Riemannian surfaces including the sphere, the hyperbolic plane, and to surfaces of bounded genus. More generally, intersection graphs of interior-disjoint geometric objects are called tangency graphs or contact graphs. As a special case, the coin graphs of packings of unit circles are called penny graphs.
Circle packings have applications in conformal mapping, the construction of polyhedra, planar separator theorems, graph drawing, and the theory of random walks. The study of the tangencies of circle packings, for which the circle packing theorem is central, should be distinguished from the study of circle packings within fixed shapes but without specified tangencies, typically studied with respect to their density (the fraction of area covered by circles).
Theorem statement and proofs A maximal planar graph is a finite simple planar graph to which no more edges can be added while preserving planarity. It may be embedded in the plane with different choices of the outer face, but all such embeddings share the same set of faces (including the outer face) which must all be triangles. The circle packing theorem guarantees the existence of a circle packing with finitely many circles whose intersection graph is isomorphic to . As the following theorem states more formally, every maximal planar graph can have at most one packing.
The geometric transformations in the uniqueness part of the theorem, reflections and Möbius transformation, preserve circles, and therefore the tangency graph of any system of circles. Uniqueness means that, for any two packings of the same maximal planar graph, there exists a transformation of these types that takes one packing into the other. For every finite planar graph , it is possible to add vertices to to construct a larger maximal planar graph in which is an induced subgraph. Constructing a circle packing from this larger graph, and then removing the circles for the added vertices, produces a circle packing for . This allows the existence of circle packings for arbitrary planar graphs to be derived from the special case for maximal planar graphs. and justify this claim by adding one vertex per face, adjacent to all vertices in the face. This is not a correct construction: It fails when a vertex has more than one incidence with a face, as happens in plane graphs that are not 2-vertex-connected. claim that two added vertices per face suffice, but do not provide details. A more complicated augmentation strategy that does not require 2-connectivity, adding a binary tree within each face and then triangulating the new faces created by this tree, is given by .
Existence Paul Koebe's original proof of the existence of a circle packing for any planar graph is based on his conformal uniformization theorem, saying that a finitely connected planar domain is conformally equivalent to a circle domain. A circle domain is a domain, a connected open subset of the plane, whose boundary components are circles or points. It is finitely connected when it has finitely many boundary components, and hence finite first Betti number (the number of generators of its fundamental group). The circle packing is a limiting case of Koebe's result, for domains complementary to the union of disks of the desired circle packing. Koebe conjectured that the finite connectivity assumption was unnecessary in his theorem but was unable to prove it. In 1993, Zheng-Xu He and Oded Schramm extended Koebe's theorem to countably connected domains, and to certain packings of countably many circles.
William Thurston's proof is based on the Brouwer fixed point theorem. Another proof uses a discrete variant of Perron's method of constructing solutions to the Dirichlet problem.; . Yves Colin de Verdière proved the existence of the circle packing as a minimizer of a convex function on a certain configuration space. Bennett Chow and Feng Luo found another proof using a combinatorial analogue of Ricci flow. As MathSciNet reviewer Igor Rivin writes, this is also the gradient flow of a function that "may well be the one introduced by Colin de Verdière".; for Rivin's review, see
Another proof starts with a circle packing with the correct number of disks but an incorrect pattern of tangencies, for which existence is easy to prove, such as an Apollonian packing. It then corrects the tangencies, one at a time, by removing one edge from the corresponding maximal planar graph and replacing it by the other diagonal of the resulting quadrilateral, at the same time adjusting the packing to match this change, in effect walking in a flip graph of triangulations, until reaching the desired graph of tangencies.
Uniqueness
Thurston observes that the uniqueness of circle packings is a consequence of the Mostow rigidity theorem. To see this, let 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.
Schramm generalized the uniqueness of circle packings to certain packings of infinitely many circles on a sphere or open disk. His uniqueness theorem applies to circle packings in which the connected components of the space outside all circles are either circular triangles or individual singular points. The graph of tangencies of such a packing and the triangles determined by the non-singular components form a triangulation of the sphere or disk, punctured at the singular points. Schramm proves that when any two packings have at most a countably infinite set of singularities and have combinatorially equivalent triangulations, they are equivalent under Möbius transformations. This uniqueness argument does not, however, characterize the triangulations for which such a packing exists.
Generalizations
A version of the circle packing applies to some infinite graphs. In particular, an infinite planar triangulation of an open disk has a locally finite packing in either the Euclidean plane or the hyperbolic plane (but not both). Here, locally finite means that every point of the plane has a neighborhood that intersects only finitely many circles. In the Euclidean case, the packing is unique up to similarity; in the hyperbolic case, it is unique up to isometry.
The circle packing theorem generalizes to graphs that are not planar. If is a graph that can be embedded on a surface (more precisely, an orientable 2-manifold), then there is a Riemannian metric of constant curvature on and a circle packing on whose contact graph is isomorphic to . If is closed (compact and without boundary) and is a triangulation of , then and the packing are unique up to conformal equivalence. If is the sphere, then its geometry is spherical geometry and the equivalence is up to Möbius transformations. If it is a torus, the geometry is locally Euclidean (as a flat torus), and the equivalence is up to scaling by a constant and isometries. If has genus at least 2, then the geometry is locally hyperbolic and the equivalence is up to isometries.
Another generalization of the circle packing theorem involves replacing the condition of tangency with a specified intersection angle between circles corresponding to neighboring vertices. One version is as follows. Suppose that is a finite 3-connected planar graph (that is, a polyhedral graph), then there is a pair of primal–dual circle packings: one packing whose intersection graph is isomorphic to , and another whose intersection graph is isomorphic to the planar dual of , such that for every vertex in and face adjacent to it, the circle in the first packing corresponding to the vertex intersects orthogonally with the circle in the second packing corresponding to the face. For instance, applying this result to the graph of the tetrahedron gives, for any four mutually tangent circles, a second set of four mutually tangent circles each of which is orthogonal to three of the first four. The circle packing for a maximal planar graph is automatically part of a pair of primal–dual circle packings, because each triple of tangent circles in the primal packing has a dual circle that passes at right angles through its three points of tangency. Like the circle packing for a maximal planar graphs, primal–dual circle packings are unique up to reflections and Möbius transformations.; ; A further generalization, replacing intersection angle with inversive distance, allows the specification of packings in which some circles are required to be disjoint from each other rather than crossing or being tangent.
Another variety of generalizations allows shapes other than circles. Suppose that each vertex of a finite planar graph corresponds to a smooth convex set . Then there is a packing in the plane whose tangencies correspond one-for-one with the edges of where each set is obtained from by translating and scaling. This result is a special case of Schramm's "monster packing theorem". The "monster" of the theorem is a spanning tree of the given graph, with a function for each vertex specifying how the shape it should be packed with depends on the relative positions of tangencies around all the shapes, satisfying certain consistency conditions. To prove that monsters can always be packed, Schramm followed Thurston's proof of the circle packing theorem, using the Brouwer fixed-point theorem. He wrote that "One can just see the terrible monster swinging its arms in sheer rage, the tentacles causing a frightful hiss, as they rub against each other."
Other properties Relative radii
A result known as the ring lemma controls the sizes of adjacent circles in a Euclidean circle packing. According to the ring lemma, if one circle in a packing is surrounded by a ring of others, then the ratio of the inner circle's radius to the smallest radius of its surrounding circles is at most exponential in . More precisely, this ratio is at most , where denotes the th Fibonacci number.; ;
Monotonicity of angles