Circle packing theorem

In other words, every maximal planar graph G is the 1-skeleton of a simplicial complex which is homeomorphic to the sphere.

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.

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.

[1] 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.

, 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.

[2] At the Bieberbach conference in 1985, William Thurston conjectured that circle packings could be used to approximate conformal mappings.

[2] Thurston's idea was to pack circles of some small radius r in a hexagonal tessellation of the plane, within region A, leaving a narrow region near the boundary of A, of width r, where no more circles of this radius can fit.

More precisely, they showed that, as n goes to infinity, the function fn determined using Thurston's method from hexagonal packings of radius-1/n circles converges uniformly on compact subsets of A to a conformal map from A to C.[2] Despite the success of Thurston's conjecture, practical applications of this method have been hindered by the difficulty of computing circle packings and by its relatively slow convergence rate.

Thurston's proof is based on Brouwer's fixed point theorem.

As a graduate student, Oded Schramm was supervised by Thurston at Princeton University.

As Rohde (2011, p. 1628) recounts, there is a "poetic description" in Schramm's dissertation of how existence for circle packing can be deduced from the fixed point theorem: "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."

There is also a proof using a discrete variant of Perron's method of constructing solutions to the Dirichlet problem.

[4] Yves Colin de Verdière proved the existence of the circle packing as a minimizer of a convex function on a certain configuration space.

An alternative proof of the planar separator theorem, originally due to Lipton and Tarjan,[6] has been obtained in this way.

[7] Another application of the circle packing theorem is that unbiased limits of bounded-degree planar graphs are almost surely recurrent.

[8] Other applications include implications for the cover time.<[9] and estimates for the largest eigenvalue of bounded-genus graphs.

[12] Fáry's theorem, that every graph that can be drawn without crossings in the plane using curved edges can also be drawn without crossings using straight line segment edges, follows as a simple corollary of the circle packing theorem: by placing vertices at the centers of the circles and drawing straight edges between them, a straight-line planar embedding is obtained.

Collins & Stephenson (2003) describe a numerical relaxation algorithm for finding circle packings, based on ideas of William Thurston.

The version of the circle packing problem that they solve takes as input a planar graph, in which all the internal faces are triangles and for which the external vertices have been labeled by positive numbers.

They begin with a set of tentative radii that do not correspond to a valid packing, and then repeatedly perform the following steps: Each of these steps may be performed with simple trigonometric calculations, and as Collins and Stephenson argue, the system of radii converges rapidly to a unique fixed point for which all covering angles are exactly 2π.

If G is a graph that can be embedded on a surface S, then there is a constant curvature Riemannian metric d on S and a circle packing on (S, d) whose contacts graph is isomorphic to G. If S is closed (compact and without boundary) and G is a triangulation of S, then (S, d) and the packing are unique up to conformal equivalence.

[15] 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.

Suppose that G = (V, E) is a finite planar graph, and to each vertex v of G corresponds a shape

One proof of this generalization can be obtained by applying Koebe's original proof[17] and the theorem of Brandt[18] and Harrington[19] stating that any finitely connected domain is conformally equivalent to a planar domain whose boundary components have specified shapes, up to translations and scaling.

Circle packings were studied as early as 1910, in the work of Arnold Emch on Doyle spirals in phyllotaxis (the mathematics of plant growth).

[17] William Thurston[1] rediscovered the circle packing theorem, and noted that it followed from the work of E. M. Andreev.

Thurston also proposed a scheme for using the circle packing theorem to obtain a homeomorphism of a simply connected proper subset of the plane onto the interior of the unit disk.

The Thurston Conjecture was later proved by Burton Rodin and Dennis Sullivan.

[21] This led to a flurry of research on extensions of the circle packing theorem, relations to conformal mappings, and applications.