Circle Packing Theorem - A Uniqueness Statement

A Uniqueness Statement

A graph G is triangulated planar if it is planar and every connected component of the complement of the embedding of G in the sphere has precisely three edges on its boundary, or in other words, if G is the 1-skeleton of a simplicial complex which is homeomorphic to the sphere. Any triangulated planar graph G is connected and simple, so the circle packing theorem guarantees the existence of a circle packing whose intersection graph is (isomorphic to) G. Such a G must also be finite, so its packing will have a finite number of circles. 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 triangulated 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. The plane in which the circles are packed may be viewed as the boundary of a halfspace model for 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 from the circles of the packing, and a second set of disjoint planes defined by the circles surrounding 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 based on the maximum principle 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 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 v be an interior vertex of G for which the circles in the two packings have sizes that are as far apart as possible: that is, choose v to maximize the ratio r₁/r₂ of the radii of its circles in the two packings. For each triangular face of G containing v, it follows that the angle at the center of the circle for 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 r₁/r₂ 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 2π in both packings, so all neighboring vertices to v must have the same ratio as 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 1, so r₁/r₂ = 1 and the two packings have identical radii for all circles.