1.2 Maximal packings
Given a complex K, there are numerous results on the existence and variety of packings for K; we need two main types. Let us begin with the extreme rigidity displayed by maximal packings.
Circle Packing Theorem
Given a complex K, there exists a unique Riemann surface X and a circle packing PK; for K. in the intrinsic metric of constant curvature on X so that PK is univalent and fills X. The packing PK is unique up to conformal automorphisms of X and is called the maximal packing for K.
This is just the Koebe–Andreev–Thurston Theorem when K triangulates a sphere; it was extended by Beardon and Stephenson to arbitrary K. of bounded degree [10] and then by He and Schramm to cases of unbounded degree [55].
Figure 4 illustrates maximal packings for several complexes. Note that each K “chooses” its own geometry: that is, K, which begins as a topological surface, is endowed with a unique conformal structure and associated metric which support PK. The complex K, is said to be spherical, parabolic, or hyperbolic depending on the curvature of that geometry.
Fig. 4. Maximal packings
We cannot go into the details of the proof, but it may be helpful to highlight some of the familiar geometric notions which are pivotal. The first case is the key, both in theory and practice.
Case I
K
, triangulates a closed topological disc
Here K. is finite, simply connected, and has a boundary. Figure 2(a) is an elementary example, and the extremal nature of its maximal packing, Figure 2(d), is visually evident – the boundary circles are horocycles, circles internally tangent to the unit circle. Indeed, horocycles are naturally interpreted as circles of infinite hyperbolic radius, so our task reduces to finding a hyperbolic packing label for K whose boundary labels are infinite.
Formally, the proof relies on monotonicity results and a “Perron” method. One defines Ф as the collection of subpacking labels for K, that is, (hyperbolic) labels R with the property that the associated angle sums for interior vertices are greater than or equal to 2π. One shows that Φ is non-empty, closed under maxima, and uniformly bounded for interior v. The upper envelope, the label R^ defined by
R^(v)=supR∈Φ{R(v)},
can be shown to be a packing label with infinite boundary radii. With these radii in hand, successively laying out the circles gives PK.
It is more informative (and practical) to approach the packing problem algorithmically. The geometric ingredients are surprisingly elementary. Consider a univalent flower in D as shown below, with central (hyperbolic) radius r and m petal radii r1, r2,…, rm; the (hyperbolic) faces are shown for reference. Then:
Monotonicity: If r is increased, then the angle sum at the center circle goes down while the angle sum at each of the petal circles goes up.
Rodin/Sullivan Ring Lemma: There’s a constant C = C(m) so that rj/r⩾ C; that is, in a (univalent) flower, no petal circle can be too much smaller than the center circle.
Bound: r ⩽ − log(sin(π/m)). In the hyperbolic plane, a circle cannot be too large if m petal circles can wrap at least once around it.
To get some taste for the reasoning, suppose we were to grant the existence of some initial hyperbolic packing P0 for K. I ask the reader to imagine the effect of increasing one of its boundary circles. It’s an interesting exercise depending solely on monotonicity; deduce an upward pressure reverberating through all of the interior radii as they adjust in order to keep their angles sums at 2π. The adjustments ultimately lead to a new packing for K. which accommodates the increased boundary circle. Iterating this increment/repack cycle allows one to push the boundary radii to ∞; monotonicity and our bound force the interior radii to converge to finite limiting values. The result is the maximal packing label RK. The argument is quite striking when implemented live on a computer screen. Figure 5(a) is an initial packing P0 for the complex of Figure 2. Incrementally increasing the boundary radii generates a succession of intermediate packings, several of which are superimposed in Figure 5(b). One can see the monotonicity at work as the maximal packing, isolated in Figure 5(c), emerges.
Fig. 5. Growing to the max.
The bound on radii for interior circles, which fails in euclidean geometry, along with the availability of circles (horocycles) having infinite radius are what make the proof click in the hyperbolic setting. The uniqueness of PK (up to automorphisms of D) can be established using monotonicity along with the association in hyperbolic geometry between “angles” and “area”. (It also follows from fixed point arguments due to He and Schramm, which we’ll comment on later.) The fact that the circles of the maximal packing have mutually disjoint interiors is a consequence of local univalence and a standard topological argument principle.
Let’s register an important observation about RK which can be spun off from the proof.
Lemma 2
Suppose K triangulates a closed topological disc. If R is any hyperbolic packing label for K, then R⩽RK, meaning that R(v)⩽RK(v) for every vertex v∈K. Moreover, equality holds at a single interior vertex if and only if R=RK.
This justifies the adjective “maximal” for PK and will shortly become the key ingredient for handling infinite complexes.
Case II
K
triangulates a sphere
The spherical case is an easy consequence of Case I. Choosing a vertex v∞ of K, form a reduced complex K′ by removing v∞ and all edges and faces containing v∞. Then K′ triangulates a closed disc, so Case I yields a maximal packing P′=PK′ in D. Stereographic projection to S2 carries P′ to a circle packing in the southern hemisphere. All its boundary circles, as projections of horocycles in D, will be tangent to the northern hemisphere, so by including that hemisphere as the circle c∞ for v∞, we have a spherical packing in S2 for K itself. A Möbius transformation can be applied for any desired normalization.
This stereographic projection argument is Thurston’s and was originally used to prove Case I from Case II. However, as you will see in the next case, the hyperbolic arguments give added value.
Case III
K
triangulates an open topological disc
Here K is infinite, simply connected, and without boundary. Designate some interior vertex v0 and exhaust K, by a nested sequence of finite simply connected complexes v0∈K1⊂K2⊂⋯→K. For each j, write Pj for the maximal packing of Kj,Rj for the maximal packing label, and r0(j) for the label at v0. Note that within the maximal packing Pj+1 lies a packing for Kj. By Lemma 2, therefore, r0(j+1)<r0(j); that is, the labels at v0 are strictly decreasing,
r0(1)>r0(2)>r0(3)>⋯.
Fig. 6. Projection to the sphere.
In other words, as more circles of K are incorporated, the circle at the origin gets smaller. That brings us to a crucial
Dichotomy:{(P):r0(j)→0,(H):r0(j)→r0(∞)forsomer0(∞)>0.
We will find that alternatives (P) and (H) correspond to parabolic and hyperbolic, respectively. It might be best to illustrate with a pair of particularly clean examples. Let K6 denote the familiar hexagonal (constant 6-degree) complex and K7, the heptagonal (constant 7-degree) complex. In each instance choose Kj to consist of vertices within j-generations of v0 and normalize Pj so that v0 is at the origin and some designated neighbor v1 is centered on the positive imaginary axis.
In Figure 7(a) I have superimposed the first few packings Pj associated with K6. Note that the circle for v0 at the origin is shrinking rather rapidly – this is alternative (P). In contrast, in Figure 7(b) I have superimposed the first few packings associated with K7; the circle at the origin again gets smaller, but very quickly stabilizes at a positive value – this is alternative (H).
Fig. 7. The hyperbolic/parabolic dichotomy.
The maximal packing PK in each case results from a “geometric” limiting process. In the heptagonal case, Figure 7(b), one can almost see the limit packing emerging. Formally, one uses the Ring Lemma to prove existence of positive limit radii for every vertex v and diagonalization to deduce limits for circle centers. It is relatively easy to show that the limit packing P is univalent and fills D. In other words, K7 is hyperbolic and the packings Pj converge to PK7.
On the other hand, it is certainly difficult to see a penny packing emerging in Figure 7(a). Indeed, in alternative (P), the Ring Lemma implies that all circle radii decrease to zero. Consequently, we shift perspective, treating each Pj as a euclidean packing and scaling it so the circle for v0 is the unit circle. Now the Ring Lemma yields positive and finite limits for all the (euclidean) radii and again diagonalization provides us with a univalent limit packing P. Thus K6 is parabolic and P=PK6, the familiar “penny” packing. The proof that carr PK6=C in the parabolic case is more difficult than it might seem. It was confirmed for K having bounded degree in [10] using quasiconformal arguments. The proof in the general case is even more subtle and was provided by He and Schramm in [55]. Their key observation? Distinct circles can intersect in at most 2 points! I can’t give details, but their arguments deserve mention not only for their elegance but for the powerful tools they bring to the discrete setting – versions of the winding number arguments so central in classical complex analysis.
If K is infinite, simply connected, but has boundary, then it falls under the hyperbolic alternative (H). With this observation, we find that we have taken care of all simply connected complexes, Case I being hyperbolic, Case II spherical, and Case III either hyperbolic or parabolic depending on combinatorics. Before going on, it is important to note the essential uniqueness of all the extremal packings obtained so far: when K is simply connected, its maximal packing PK is unique up to Möbius transformations of the sphere, plane, or disc, as appropriate.
Case IV
K
triangulates a surface S
We assume that S is an oriented topological surface and, in view of our earlier cases, that S is not simply connected. It is well known that a triangulation K of S can be lifted to a complex K˜ triangulating the universal covering surface S˜ of S. There is an associated simplicial projection p:K˜→K and a group G of simplicial automorphisms g:K˜→K, satisfying p ∘ g ≡ p.
K˜ is simply connected, and since the sphere covers only itself, K˜ must be an infinite triangulation of a topological disc, Case III. Let D denote the plane or disc, depending on whether K˜ is parabolic or hyperbolic, and let P˜=PK˜ denote the maximal packing in D for K˜. The situation is illustrated in Figure 8 for a hyperbolic case. The circle packing shown in D is just the part of the infinite packing P˜ associated with a fundamental domain for the covering p.
Fig. 8. Discrete covering map.
The essential uniqueness of P˜ in D becomes the key ingredient as we deploy a standard arrow-chasing argument. Briefly, each simplicial automorphism g of K˜ must induce a Möbius transformation Mg of D which maps the packing P˜ to itself. Γ = {Mg: g ∈ G} is a discrete group of Möbius transformations of D isomorphic to G. Let X denote the Riemann surface D/Γ obtained in the classical manner from D by identifying all points equivalent modulo Γ, and write π:D→X for the analytic covering projection. As topological surfaces, X and S are homeomorphic, however X inherits a conformal structure and conformal metric from D under π. This “intrinsic” metric is either hyperbolic or euclidean, depending on D, and each circle in D projects, a fortiori, to a “circle” in the intrinsic metric on X. Clearly, the projected circles π(P˜) in X provide an in situ packing for K. This is precisely the maximal packing PK we have been looking for.
This concludes our overview of maximal packings. Even in this last case, note that X is uniquely determined among all Riemann surfaces homeomorphic to S based purely on the combinatorics of K, so the take-home message is that K again “chooses” the appropriate geometry for its maximal packing.
