246C notes 2: Circle packings, conformal maps, and quasiconformal maps

12 April, 2018 in 246C - complex analysis, math.CV, math.MG | Tags: circle packing, quasiconformal mapping, Riemann mapping theorem

Previous set of notes: Notes 1. Next set of notes: Notes 3.

We now leave the topic of Riemann surfaces, and turn now to the (loosely related) topic of conformal mapping (and quasiconformal mapping). Recall that a conformal map ${f: U \rightarrow V}$ from an open subset ${U}$ of the complex plane to another open set ${V}$ is a map that is holomorphic and bijective, which (by Rouché’s theorem) also forces the derivative of ${f}$ to be nowhere vanishing. We then say that the two open sets ${U,V}$ are conformally equivalent. From the Cauchy-Riemann equations we see that conformal maps are orientation-preserving and angle-preserving; from the Newton approximation ${f( z_0 + \Delta z) \approx f(z_0) + f'(z_0) \Delta z + O( |\Delta z|^2)}$ we see that they almost preserve small circles, indeed for ${\varepsilon}$ small the circle ${\{ z: |z-z_0| = \varepsilon\}}$ will approximately map to ${\{ w: |w - f(z_0)| = |f'(z_0)| \varepsilon \}}$ .

In previous quarters, we proved a fundamental theorem about this concept, the Riemann mapping theorem:

Theorem 1 (Riemann mapping theorem) Let ${U}$ be a simply connected open subset of ${{\bf C}}$ that is not all of ${{\bf C}}$ . Then ${U}$ is conformally equivalent to the unit disk ${D(0,1)}$ .

This theorem was proven in these 246A lecture notes, using an argument of Koebe. At a very high level, one can sketch Koebe’s proof of the Riemann mapping theorem as follows: among all the injective holomorphic maps ${f: U \rightarrow D(0,1)}$ from ${U}$ to ${D(0,1)}$ that map some fixed point ${z_0 \in U}$ to ${0}$ , pick one that maximises the magnitude ${|f'(z_0)|}$ of the derivative (ignoring for this discussion the issue of proving that a maximiser exists). If ${f(U)}$ avoids some point in ${D(0,1)}$ , one can compose ${f}$ with various holomorphic maps and use Schwarz’s lemma and the chain rule to increase ${|f'(z_0)|}$ without destroying injectivity; see the previous lecture notes for details. The conformal map ${\phi: U \rightarrow D(0,1)}$ is unique up to Möbius automorphisms of the disk; one can fix the map by picking two distinct points ${z_0,z_1}$ in ${U}$ , and requiring ${\phi(z_0)}$ to be zero and ${\phi(z_1)}$ to be positive real.

It is a beautiful observation of Thurston that the concept of a conformal mapping has a discrete counterpart, namely the mapping of one circle packing to another. Furthermore, one can run a version of Koebe’s argument (using now a discrete version of Perron’s method) to prove the Riemann mapping theorem through circle packings. In principle, this leads to a mostly elementary approach to conformal geometry, based on extremely classical mathematics that goes all the way back to Apollonius. However, in order to prove the basic existence and uniqueness theorems of circle packing, as well as the convergence to conformal maps in the continuous limit, it seems to be necessary (or at least highly convenient) to use much more modern machinery, including the theory of quasiconformal mapping, and also the Riemann mapping theorem itself (so in particular we are not structuring these notes to provide a completely independent proof of that theorem, though this may well be possible).

To make the above discussion more precise we need some notation.

Definition 2 (Circle packing) A (finite) circle packing is a finite collection ${(C_j)_{j \in J}}$ of circles ${C_j = \{ z \in {\bf C}: |z-z_j| = r_j\}}$ in the complex numbers indexed by some finite set ${J}$ , whose interiors are all disjoint (but which are allowed to be tangent to each other), and whose union is connected. The nerve of a circle packing is the finite graph whose vertices ${\{z_j: j \in J \}}$ are the centres of the circle packing, with two such centres connected by an edge if the circles are tangent. (In these notes all graphs are undirected, finite and simple, unless otherwise specified.)

It is clear that the nerve of a circle packing is connected and planar, since one can draw the nerve by placing each vertex (tautologically) in its location in the complex plane, and drawing each edge by the line segment between the centres of the circles it connects (this line segment will pass through the point of tangency of the two circles). Later in these notes we will also have to consider some infinite circle packings, most notably the infinite regular hexagonal circle packing.

The first basic theorem in the subject is the following converse statement:

Theorem 3 (Circle packing theorem) Every connected planar graph is the nerve of a circle packing.

Among other things, the circle packing theorem thus implies as a corollary Fáry’s theorem that every planar graph can be drawn using straight lines.

Of course, there can be multiple circle packings associated to a given connected planar graph; indeed, since reflections across a line and Möbius transformations map circles to circles (or lines), they will map circle packings to circle packings (unless one or more of the circles is sent to a line). It turns out that once one adds enough edges to the planar graph, the circle packing is otherwise rigid:

Theorem 4 (Koebe-Andreev-Thurston theorem) If a connected planar graph is maximal (i.e., no further edge can be added to it without destroying planarity), then the circle packing given by the above theorem is unique up to reflections and Möbius transformations.

Exercise 5 Let ${G}$ be a connected planar graph with ${n \geq 3}$ vertices. Show that the following are equivalent:

(i) ${G}$ is a maximal planar graph.

(ii) ${G}$ has ${3n-6}$ edges.

(iii) Every drawing ${D}$ of ${G}$ divides the plane into faces that have three edges each, and each edge is adjacent to two distinct faces. (This includes one unbounded face.)

(iv) At least one drawing ${D}$ of ${G}$ divides the plane into faces that have three edges each, and each edge is adjacent to two distinct faces.

(Hint: you may use without proof Euler’s formula ${V-E+F=2}$ for planar graphs, where ${F}$ is the number of faces including the unbounded face.)

Thurston conjectured that circle packings can be used to approximate the conformal map arising in the Riemann mapping theorem. Here is an informal statement:

Conjecture 6 (Informal Thurston conjecture) Let ${U}$ be a simply connected domain, with two distinct points ${z_0,z_1}$ . Let ${\phi: U \rightarrow D(0,1)}$ be the conformal map from ${U}$ to ${D(0,1)}$ that maps ${z_0}$ to the origin and ${z_1}$ to a positive real. For any small ${\varepsilon>0}$ , let ${{\mathcal C}_\varepsilon}$ be the portion of the regular hexagonal circle packing by circles of radius ${\varepsilon}$ that are contained in ${U}$ , and let ${{\mathcal C}'_\varepsilon}$ be an circle packing of ${D(0,1)}$ with the same nerve (up to isomorphism) as ${{\mathcal C}_\varepsilon}$ , with all “boundary circles” tangent to ${D(0,1)}$ , giving rise to an “approximate map” ${\phi_\varepsilon: U_\varepsilon \rightarrow D(0,1)}$ defined on the subset ${U_\varepsilon}$ of ${U}$ consisting of the circles of ${{\mathcal C}_\varepsilon}$ , their interiors, and the interstitial regions between triples of mutually tangent circles. Normalise this map so that ${\phi_\varepsilon(z_0)}$ is zero and ${\phi_\varepsilon(z_1)}$ is a positive real. Then ${\phi_\varepsilon}$ converges to ${\phi}$ as ${\varepsilon \rightarrow 0}$ .

A rigorous version of this conjecture was proven by Rodin and Sullivan. Besides some elementary geometric lemmas (regarding the relative sizes of various configurations of tangent circles), the main ingredients are a rigidity result for the regular hexagonal circle packing, and the theory of quasiconformal maps. Quasiconformal maps are what seem on the surface to be a very broad generalisation of the notion of a conformal map. Informally, conformal maps take infinitesimal circles to infinitesimal circles, whereas quasiconformal maps take infinitesimal circles to infinitesimal ellipses of bounded eccentricity. In terms of Wirtinger derivatives, conformal maps obey the Cauchy-Riemann equation ${\frac{\partial \phi}{\partial \overline{z}} = 0}$ , while (sufficiently smooth) quasiconformal maps only obey an inequality ${|\frac{\partial \phi}{\partial \overline{z}}| \leq \frac{K-1}{K+1} |\frac{\partial \phi}{\partial z}|}$ . As such, quasiconformal maps are considerably more plentiful than conformal maps, and in particular it is possible to create piecewise smooth quasiconformal maps by gluing together various simple maps such as affine maps or Möbius transformations; such piecewise maps will naturally arise when trying to rigorously build the map ${\phi_\varepsilon}$ alluded to in the above conjecture. On the other hand, it turns out that quasiconformal maps still have many vestiges of the rigidity properties enjoyed by conformal maps; for instance, there are quasiconformal analogues of fundamental theorems in conformal mapping such as the Schwarz reflection principle, Liouville’s theorem, or Hurwitz’s theorem. Among other things, these quasiconformal rigidity theorems allow one to create conformal maps from the limit of quasiconformal maps in many circumstances, and this will be how the Thurston conjecture will be proven. A key technical tool in establishing these sorts of rigidity theorems will be the theory of an important quasiconformal (quasi-)invariant, the conformal modulus (or, equivalently, the extremal length, which is the reciprocal of the modulus).

— 1. Proof of the circle packing theorem —

We loosely follow the treatment of Beardon and Stephenson. It is slightly more convenient to temporarily work in the Riemann sphere ${{\bf C} \cup \{\infty\}}$ rather than the complex plane ${{\bf C}}$ , in order to more easily use Möbius transformations. (Later we will make another change of venue, working in the Poincaré disk ${D(0,1)}$ instead of the Riemann sphere.)

Define a Riemann sphere circle to be either a circle in ${{\bf C}}$ or a line in ${{\bf C}}$ together with ${\infty}$ , together with one of the two components of the complement of this circle or line designated as the “interior”. In the case of a line, this “interior” is just one of the two half-planes on either side of the line; in the case of the circle, this is either the usual interior or the usual exterior plus the point at infinity; in the last case, we refer to the Riemann sphere circle as an exterior circle. (One could also equivalently work with an orientation on the circle rather than assigning an interior, since the interior could then be described as the region to (say) the left of the circle as one traverses the circle along the indicated orientation.) Note that Möbius transforms map Riemann sphere circles to Riemann sphere circles. If one views the Riemann sphere as a geometric sphere in Euclidean space ${{\bf R}^3}$ , then Riemann sphere circles are just circles on this geometric sphere, which then have a centre on this sphere that lies in the region designated as the interior of the circle. We caution though that this “Riemann sphere” centre does not always correspond to the Euclidean notion of the centre of a circle. For instance, the real line, with the upper half-plane designated as interior, will have ${i}$ as its Riemann sphere centre; if instead one designates the lower half-plane as the interior, the Riemann sphere centre will now be ${-i}$ . We can then define a Riemann sphere circle packing in exact analogy with circle packings in ${{\bf C}}$ , namely finite collections of Riemann sphere circles whose interiors are disjoint and whose union is connected; we also define the nerve as before. This is now a graph that can be drawn in the Riemann sphere, using great circle arcs in the Riemann sphere rather than line segments; it is also planar, since one can apply a Möbius transformation to move all the points and edges of the drawing away from infinity.

By Exercise 5, a maximal planar graph with at least three vertices can be drawn as a triangulation of the Riemann sphere. If there are at least four vertices, then it is easy to see that each vertex has degree at least three (a vertex of degree zero, one or two in a triangulation with simple edges will lead to a connected component of at most three vertices). It is a topological fact, not established here, that any two triangulations of such a graph are homotopic up to reflection (to reverse the orientation). If a Riemann sphere circle packing has the nerve of a maximal planar graph ${G}$ of at least four vertices, then we see that this nerve induces an explicit triangulation of the Riemann sphere by connecting the centres of any pair of tangent circles with the great circle arc that passes through the point of tangency. If ${G}$ was not maximal, one no longer gets a triangulation this way, but one still obtains a partition of the Riemann sphere into spherical polygons.

We remark that the triangles in this triangulation can also be described purely from the abstract graph ${G}$ . Define a triangle in ${G}$ to be a triple ${w_1,w_2,w_3}$ of vertices in ${G}$ which are all adjacent to each other, and such that the removal of these three vertices from ${G}$ does not disconnect the graph. One can check that there is a one-to-one correspondence between such triangles in a maximal planar graph ${G}$ and the triangles in any Riemann sphere triangulation of this graph.

Theorems 3, 4 are then a consequence of

Theorem 7 (Riemann sphere circle packing theorem) Let ${G}$ be a maximal planar graph with at least four vertices, drawn as a triangulation of the Riemann sphere. Then there exists a Riemann sphere circle packing with nerve ${G}$ whose triangulation is homeomorphic (in an orientation preserving fashion) to the given triangulation. Furthermore, this packing is unique up to Möbius transformations.

Exercise 8 Deduce Theorems 3, 4 from Theorem 7. (Hint: If one has a non-maximal planar graph for Theorem 3, add a vertex at the interior of each non-triangular face of a drawing of that graph, and connect that vertex to the vertices of the face, to create a maximal planar graph to which Theorem 4 or Theorem 7 can be applied. Then delete these “helper vertices” to create a packing of the original planar graph that does not contain any “unwanted” tangencies. You may use without proof the above assertion that any two triangulations of a maximal planar graph are homotopic up to reflection.)

Exercise 9 Verify Theorem 7 when ${G}$ has exactly four vertices. (Hint: for the uniqueness, one can use Möbius transformations to move two of the circles to become parallel lines. Here you can assume without proof that any two drawings of a maximal planar graph are homeomorphic.)

To prove this theorem, we will make a reduction with regards to the existence component of Theorem 7. For technical reasons we will need to introduce a notion of non-degeneracy. Let ${G}$ be a maximal planar graph with at least five vertices, and let ${v}$ be a vertex in ${G}$ . As discussed above, the degree ${d}$ of ${v}$ is at least three. Writing the neighbours of ${v}$ in clockwise or counterclockwise order (with respect to a triangulation) as ${v_1,\dots,v_d}$ (starting from some arbitrary neighbour), we see that each ${v_i}$ is adjacent to ${v_{i-1}}$ and ${v_{i+1}}$ (with the conventions ${v_0=v_d}$ and ${v_{d+1}=v_1}$ ). We say that ${v}$ is non-degenerate if there are no further adjacencies between the ${v_1,\dots,v_d}$ , and if there is at least one further vertex in ${G}$ besides ${v,v_1,\dots,v_d}$ . Here is another characterisation:

Exercise 10 Let ${G}$ be a maximal planar graph with at least five vertices, let ${v}$ be a vertex in ${G}$ , and let ${v_1,\dots,v_d}$ be the neighbours of ${v}$ . Show that the following are equivalent:

(i) ${v}$ is non-degenerate.

(ii) The graph ${G \backslash \{ v, v_1, \dots, v_d \}}$ is connected and non-empty, and every vertex in ${v_1,\dots,v_d}$ is adjacent to at least one vertex in ${G \backslash \{ v, v_1, \dots, v_d \}}$ .

We will then derive Theorem 7 from

Theorem 11 (Inductive step) Let ${G}$ be a maximal planar graph with at least five vertices ${V}$ , drawn as a triangulation of the Riemann sphere. Let ${v}$ be a non-degenerate vertex of ${G}$ , and let ${G - \{v\}}$ be the graph formed by deleting ${v}$ (and edges emenating from ${v}$ ) from ${G}$ . Suppose that there exists a Riemann sphere circle packing ${(C_w)_{w \in V \backslash \{v\}}}$ whose nerve is at least ${G - \{v\}}$ (that is, ${C_w}$ and ${C_{w'}}$ are tangent whenever ${w,w'}$ are adjacent in ${G - \{v\}}$ , although we also allow additional tangencies), and whose associated subdivision of the Riemann sphere into spherical polygons is homeomorphic (in orientation-preserving fashion) to the given triangulation with ${v}$ removed. Then there is a Riemann sphere circle packing ${(\tilde C_w)_{w \in V}}$ with nerve ${G}$ whose triangulation is homeomorphic (in orientation preserving fashion) to the given triangulation. Furthermore this circle packing ${(\tilde C_w)_{w \in V}}$ is unique up to Möbius transformations.

Let us now see how Theorem 7 follows from Theorem 11. Fix ${G}$ as in Theorem 7. By Exercise 9 and induction we may assume that ${G}$ has at least five vertices, and that the claim has been proven for any smaller number of vertices.

First suppose that ${G}$ contains a non-degenerate vertex ${v}$ . Let ${v_1,\dots,v_d}$ be the the neighbours of ${v}$ . One can then form a new graph ${G'}$ with one fewer vertex by deleting ${v}$ , and then connecting ${v_3,\dots,v_{d-1}}$ to ${v_1}$ (one can think of this operation as contracting the edge ${\{v,v_1\}}$ to a point). One can check that this is still a maximal planar graph that can triangulate the Riemann sphere in a fashion compatible with the original triangulation of ${G}$ (in that all the common vertices, edges, and faces are unchanged). By induction hypothesis, ${G'}$ is the nerve of a circle packing that is compatible with this triangulation, and hence this circle packing has nerve at least ${G - \{v\}}$ . Applying Theorem 11, we then obtain the required claim for ${G}$ .

Now suppose that ${G}$ contains a degenerate vertex ${v}$ . Let ${v_1,\dots,v_d}$ be the neighbours of ${v}$ traversed in order. By hypothesis, there is an additional adjacency between the ${v_1,\dots,v_d}$ ; by relabeling we may assume that ${v_1}$ is adjacent to ${v_k}$ for some ${3 \leq k \leq d-1}$ . The vertices ${V}$ in ${G}$ can then be partitioned as

$\displaystyle V = \{v\} \cup \{ v_1,\dots,v_d\} \cup V_1 \cup V_2$

where ${V_1}$ denotes those vertices in ${V \backslash \{ v_1,\dots,v_d\}}$ that lie in the region enclosed by the loop ${v_1,\dots,v_k, v_1}$ that does not contain ${v}$ , and ${V_2}$ denotes those vertices in ${V \backslash \{ v_1,\dots,v_d\}}$ that lie in the region enclosed by the loop ${v_k,\dots,v_d,v_1, v_k}$ that does not contain ${v}$ . One can then form two graphs ${G_1, G_2}$ , formed by restricting ${G}$ to the vertices ${\tilde V_1 := \{v, v_1,\dots,v_k\} \cup V_1}$ and ${\tilde V_2 := \{ v, v_k, \dots, v_d, v_1\} \cup V_2}$ respectively; furthermore, these graphs are also maximal planar (with triangulations that are compatible with those of ${G}$ ). By induction hypothesis, we can find a circle packing ${(C_w)_{w \in \tilde V_1}}$ with nerve ${G_1}$ , and a circle packing ${(C'_w)_{w \in \tilde V_2}}$ with nerve ${G_2}$ . Note that the circles ${C_v, C_{v_1}, C_{v_k}}$ are mutually tangent, as are ${C'_v, C'_{v_1}, C'_{v_k}}$ . By applying a Möbius transformation one may assume that these circles agree, thus (cf. Exercise 9) ${C_v = C'_v}$ , ${C_{v_1} = C'_{v_1}, C_{v_k} = C'_{v_k}}$ . The complement of the these three circles (and their interiors) determine two connected “interstitial” regions (that are in the shape of an arbelos, up to Möbius transformation); one can check that the remaining circles in ${(C_w)_{w \in \tilde V_1}}$ will lie in one of these regions, and the remaining circles in ${(C'_w)_{w \in \tilde V_2}}$ lie in the other. Hence one can glue these circle packings together to form a single circle packing with nerve ${G}$ , which is homeomorphic (in orientation-preserving fashion) to the given triangulation. Also, since a Möbius transformation that fixes three mutually tangent circles has to be the identity, the uniqueness of this circle packing up to Möbius transformations follows from the uniqueness for the two component circle packings ${(C_w)_{w \in \tilde V_1}}$ , ${(C'_w)_{w \in \tilde V_2}}$ .
It remains to prove Theorem 11. To help fix the freedom to apply Möbius transformations, we can normalise the target circle packing ${(\tilde C_w)_{w \in V}}$ so that ${\tilde C_v}$ is the exterior circle ${\{ |z|=1\}}$ , thus all the other circles ${\tilde C_w}$ in the packing will lie in the closed unit disk ${\overline{D(0,1)}}$ . Similarly, by applying a suitable Möbius transformation one can assume that ${\infty}$ lies outside of the interior of all the circles ${C_w}$ in the original packing, and after a scaling one may then assume that all the circles ${C_w}$ lie in the unit disk ${D(0,1)}$ .

At this point it becomes convenient to switch from the “elliptic” conformal geometry of the Riemann sphere ${{\bf C} \cup \{\infty\}}$ to the “hyperbolic” conformal geometry of the unit disk ${D(0,1)}$ . Recall that the Möbius transformations that preserve the disk ${D(0,1)}$ are given by the maps

$\displaystyle z \mapsto e^{i\theta} \frac{z-\alpha}{1-\overline{\alpha} z} \ \ \ \ \ (1)$

for real ${\theta}$ and ${\alpha \in D(0,1)}$ (see Theorem 19 of these notes). It comes with a natural metric that interacts well with circles:

Exercise 12 Define the Poincaré distance ${d(z_1,z_2)}$ between two points of ${D(0,1)}$ by the formula

$\displaystyle d(z_1,z_2) := 2 \mathrm{arctanh} |\frac{z_1-z_2}{1-z_1 \overline{z_2}}|.$

Given a measurable subset ${E}$ of ${D(0,1)}$ , define the hyperbolic area of ${E}$ to be the quantity

$\displaystyle \mathrm{area}(E) := \int_E \frac{4\ dx dy}{(1-|z|^2)^2}$

where ${dx dy}$ is the Euclidean area element on ${D(0,1)}$ .

(i) Show that the Poincaré distance is invariant with respect to Möbius automorphisms of ${D(0,1)}$ , thus ${d(Tz_1, Tz_2) = d(z_1,z_2)}$ whenever ${T}$ is a transformation of the form (1). Similarly show that the hyperbolic area is invariant with respect to such transformations.

(ii) Show that the Poincaré distance defines a metric on ${D(0,1)}$ . Furthermore, show that any two distinct points ${z_1,z_2}$ are connected by a unique geodesic, which is a portion of either a line or a circle that meets the unit circle orthogonally at two points. (Hint: use the symmetries of (i) to normalise the points one is studying.) Here, by geodesic we mean a curve that can be parameterized as ${\gamma: [a,b] \rightarrow D(0,1)}$ for some curve ${\gamma}$ for which ${d(\gamma(s),\gamma(t))}$ is proportional to ${|s-t|}$ , thus there exists ${c>0}$ such that ${d(\gamma(s),\gamma(t)) = c|s-t|}$ for all ${s,t \in [a,b]}$ .

(iii) If ${C}$ is a circle in the interior of ${D(0,1)}$ , show that there exists a point ${z_C}$ in ${D(0,1)}$ and a positive real number ${r_C}$ (which we call the hyperbolic center and hyperbolic radius respectively) such that ${C = \{ z \in D(0,1): d(z,z_C) = r_C \}}$ . (In general, the hyperbolic center and radius will not quite agree with their familiar Euclidean counterparts.) Conversely, show that for any ${z_C \in D(0,1)}$ and ${r_C > 0}$ , the set ${\{ z \in D(0,1): d(z,z_C) = r_C \}}$ is a circle in ${D(0,1)}$ .

(iv) If two circles ${C_1, C_2}$ in ${D(0,1)}$ are externally tangent, show that the geodesic connecting the hyperbolic centers ${z_{C_1}, z_{C_2}}$ passes through the point of tangency, orthogonally to the two tangent circles.

Exercise 13 (Schwarz-Pick theorem) Let ${f: D(0,1) \rightarrow D(0,1)}$ be a holomorphic map. Show that ${d(f(z_1),f(z_2)) \leq d(z_1,z_2)}$ for all ${z_1,z_2 \in D(0,1)}$ . If ${z_1 \neq z_2}$ , show that equality occurs if and only if ${f}$ is a Möbius automorphism (1) of ${D(0,1)}$ . (This result is known as the Schwarz-Pick theorem.)

We will refer to circles that lie in the closure ${\overline{D(0,1)}}$ of the unit disk as hyperbolic circles. These can be divided into the finite radius hyperbolic circles, which lie in the interior of the unit disk (as per part (iii) of the above exercise), and the horocycles, which are internally tangent to the unit circle. By convention, we view horocycles as having infinite radius, and having center at their point of tangency to the unit circle; they can be viewed as the limiting case of finite radius hyperbolic circles when the radius goes to infinity and the center goes off to the boundary of the disk (at the same rate as the radius, as measured with respect to the Poincaré distance). We write ${C(p,r)}$ for the hyperbolic circle with hyperbolic centre ${p}$ and hyperbolic radius ${r}$ (thus either ${0 < r < \infty}$ and ${p \in D(0,1)}$ , or ${r = \infty}$ and ${p}$ is on the unit circle); there is an annoying caveat that when ${r=\infty}$ there is more than one horocycle ${C(p,\infty)}$ with hyperbolic centre ${p}$ , but we will tolerate this breakdown of functional dependence of ${C}$ on ${p}$ and ${r}$ in order to simplify the notation. A hyperbolic circle packing is a circle packing ${(C(p_v,r_v))_{v \in V}}$ in which all circles are hyperbolic circles.

We also observe that the geodesic structure extends to the boundary of the unit disk: for any two distinct points ${z_1,z_2}$ in ${\overline{D(0,1)}}$ , there is a unique geodesic that connects them.

In view of the above discussion, Theorem 7 may now be formulated as follows:

Theorem 14 (Inductive step, hyperbolic formulation) Let ${G}$ be a maximal planar graph with at least four vertices ${V}$ , let ${v}$ be a non-degenerate vertex of ${G}$ , and let ${v_1,\dots,v_d}$ be the vertices adjacent to ${v}$ . Suppose that there exists a hyperbolic circle packing ${(C(p_w,r_w))_{w \in V \backslash \{v\}}}$ whose nerve is at least ${G - \{v\}}$ . Then there is a hyperbolic circle packing ${(C(\tilde p_w,\tilde r_w))_{V \backslash \{v\}}}$ homeomorphic (in orientation-preserving fashion) to ${(C(p_w,r_w))_{w \in V \backslash \{v\}}}$ such that the boundary circles ${C(\tilde p_{v_j}, \tilde r_{v_j})}$ , ${j=1,\dots,d}$ are all horocycles. Furthermore, this packing is unique up to Möbius automorphisms (1) of the disk ${D(0,1)}$ .

Indeed, once one adjoints the exterior unit circle to ${(C(p_w,r_w))_{w \in V \backslash \{v\}}}$ , one obtains a Riemann sphere circle packing whose nerve is at least ${G}$ , and hence equal to ${G}$ since ${G}$ is maximal.

To prove this theorem, the intuition is to “inflate” the hyperbolic radius of the circles of ${C_w}$ until the boundary circles all become infinite radius (i.e., horocycles). The difficulty is that one cannot just arbitrarily increase the radius of any given circle without destroying the required tangency properties. The resolution to this difficulty given in the work of Beardon and Stephenson that we are following here was inspired by Perron’s method of subharmonic functions, in which one faced an analogous difficulty that one could not easily manipulate a harmonic function without destroying its harmonicity. There, the solution was to work instead with the more flexible class of subharmonic functions; here we similarly work with the concept of a subpacking.

We will need some preliminaries to define this concept precisely. We first need some hyperbolic trigonometry. We define a hyperbolic triangle to be the solid (and closed) region in ${\overline{D(0,1)}}$ enclosed by three distinct points ${z_1,z_2,z_3}$ in ${\overline{D(0,1)}}$ and the geodesic arcs connecting them. (Note that we allow one or more of the vertices to be on the boundary of the disk, so that the sides of the triangle could have infinite length.) Let ${T := (0,+\infty]^3 \backslash \{ (\infty,\infty,\infty)\}}$ be the space of triples ${(r_1,r_2,r_3)}$ with ${0 < r_1,r_2,r_3 \leq \infty}$ and not all of ${r_1,r_2,r_3}$ infinite. We say that a hyperbolic triangle with vertices ${p_1,p_2,p_3}$ is a ${(r_1,r_2,r_3)}$ -triangle if there are hyperbolic circles ${C(p_i,r_1), C(p_2,r_2), C(p_3,r_3)}$ with the indicated hyperbolic centres and hyperbolic radii that are externally tangent to each other; note that this implies that the sidelengths opposite ${p_1,p_2,p_3}$ have length ${r_2+r_3, r_1+r_3, r_1+r_2}$ respectively (see Figure 3 of Beardon and Stephenson). It is easy to see that for any ${(r_1,r_2,r_3) \in T}$ , there exists a unique ${(r_1,r_2,r_3)}$ -triangle in ${\overline{D(0,1)}}$ up to reflections and Möbius automorphisms (use Möbius transforms to fix two of the hyperbolic circles, and consider all the circles externally tangent to both of these circles; the case when one or two of the ${r_1,r_2,r_3}$ are infinite may need to be treated separately.). As a consequence, there is a well defined angle ${\alpha_i(r_1,r_2,r_3) \in [0,\pi)}$ for ${i=1,2,3}$ subtended by the vertex ${p_i}$ of an ${(r_1,r_2,r_3)}$ triangle. We need some basic facts from hyperbolic geometry:

Exercise 15 (Hyperbolic trigonometry)

(i) (Hyperbolic cosine rule) For any ${0 < r_1,r_2,r_3 < \infty}$ , show that the quantity ${\cos \alpha_1(r_1,r_2,r_3)}$ is equal to the ratio
$\displaystyle \frac{\cosh( r_1+r_2) \cosh(r_1+r_3) - \cosh(r_2+r_3)}{\sinh(r_1+r_2) \sinh(r_1+r_3)}.$

Furthermore, establish the limiting angles

$\displaystyle \alpha_1(\infty,r_2,r_3) = \alpha_1(\infty,\infty,r_3) = \alpha_1(\infty,r_2,\infty) = 0$

$\displaystyle \cos \alpha_1(r_1,\infty,r_3) = \frac{\cosh(r_1+r_3) - \exp(r_3-r_1)}{\sinh(r_1+r_3)}$

$\displaystyle \cos \alpha_1(r_1,r_2,\infty) = \frac{\cosh(r_1+r_2) - \exp(r_2-r_1)}{\sinh(r_1+r_2)}$

$\displaystyle \cos \alpha_1(r_1,\infty,\infty) = 1 - 2\exp(-2r_1).$

(Hint: to facilitate computations, use a Möbius transform to move the ${p_1}$ vertex to the origin when the radius there is finite.) Conclude in particular that ${\alpha_1: T \rightarrow [0,\pi)}$ is continuous (using the topology of the extended real line for each component of ${T}$ ). Discuss how this rule relates to the Euclidean cosine rule in the limit as ${r_1,r_2,r_3}$ go to zero. Of course, by relabeling one obtains similar formulae for ${\alpha_2(r_1,r_2,r_3)}$ and ${\alpha_3(r_1,r_2,r_3)}$ .

(ii) (Area rule) Show that the area of a hyperbolic triangle is given by ${\pi - \alpha_1-\alpha_2-\alpha_3}$ , where ${\alpha_1,\alpha_2,\alpha_3}$ are the angles of the hyperbolic triangle. (Hint: there are several ways to proceed. For instance, one can prove this for small hyperbolic triangles (of diameter ${O(\varepsilon)}$ ) up to errors of size ${o(\varepsilon^2)}$ after normalising as in (ii), and then establish the general case by subdividing a large hyperbolic triangle into many small hyperbolic triangles. This rule is also a special case of the Gauss-Bonnet theorem in Riemannian geometry. One can also first establish the case when several of the radii are infinite, and use that to derive finite cases.) In particular, the area ${\mathrm{Area}(r_1,r_2,r_3)}$ of a ${(r_1,r_2,r_3)}$ -triangle is given by the formula
$\displaystyle \pi - \alpha_1(r_1,r_2,r_3) - \alpha_2(r_1,r_2,r_3) - \alpha_3(r_1,r_2,r_3). \ \ \ \ \ (2)$

(iii) Show that the area of the interior of a hyperbolic circle ${C(p,r)}$ with ${r<\infty}$ is equal to ${4\pi \sinh^2(r/2)}$ .

Henceforth we fix ${G, v, v_1,\dots,v_d, {\mathcal C} = (C(p_w,r_w))_{w \in V \backslash \{v\}}}$ as in Theorem 14. We refer to the vertices ${v_1,\dots,v_d}$ as boundary vertices of ${G - \{v\}}$ and the remaining vertices as interior vertices; edges between boundary vertices are boundary edges, all other edges will be called interior edges (including edges that have one vertex on the boundary). Triangles in ${G -\{v\}}$ that involve two boundary vertices (and thus necessarily one interior vertex) will be called boundary triangles; all other triangles (including ones that involve one boundary vertex) will be called interior triangles. To any triangle ${w_1,w_2,w_3}$ of ${G - \{v\}}$ , we can form the hyperbolic triangle ${\Delta_{\mathcal C}(w_1,w_2,w_3)}$ with vertices ${p_{w_1}, p_{w_2}, p_{w_3}}$ ; this is an ${(r_{w_1}, r_{w_2}, r_{w_3})}$ -triangle. Let ${\Sigma}$ denote the collection of such hyperbolic triangles; because ${{\mathcal C}}$ is a packing, we see that these triangles have disjoint interiors. They also fit together in the following way: if ${e}$ is a side of a hyperbolic triangle in ${\Sigma}$ , then there will be another hyperbolic triangle in ${\Sigma}$ that shares that side precisely when ${e}$ is associated to an interior edge of ${G - \{v\}}$ . The union of all these triangles is homeomorphic to the region formed by starting with a triangulation of the Riemann sphere by ${G}$ and removing the triangles containing ${v}$ as a vertex, and is therefore homeomorphic to a disk. One can think of the collection ${\Sigma}$ of hyperbolic triangles, together with the vertices and edges shared by these triangles, as a two-dimensional (hyperbolic) simplicial complex, though we will not develop the full machinery of such complexes here.

Our objective is to find another hyperbolic circle packing ${\tilde {\mathcal C} = (C(\tilde p_w, \tilde r_w))_{w \in V \backslash \{v\}}}$ homeomorphic (in orientation-preserving fashion) to the existing circle packing ${{\mathcal C}}$ , such at all the boundary circles (circles centred at boundary vertices) are horocycles. We observe that such a hyperbolic circle packing is completely described (up to Möbius transformations) by the hyperbolic radii ${(\tilde r_w)_{w \in V \backslash \{v\}}}$ of these circles. Indeed, suppose one knows the values of these hyperbolic radii. Then each hyperbolic triangle ${\Delta_{\mathcal C}(w_1,w_2,w_3)}$ in ${\Sigma}$ is associated to a hyperbolic triangle ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ whose sides and angles are known from Exercise 15. As the orientation of each hyperbolic triangle is fixed, each hyperbolic triangle is determined up to a Möbius automorphism of ${D(0,1)}$ . Once one fixes one hyperbolic triangle, the adjacent hyperbolic triangles (that share a common side with the first triangle) are then also fixed; continuing in this fashion we see that the entire hyperbolic circle packing ${\tilde {\mathcal C}}$ is determined.

On the other hand, not every choice of radii ${(\tilde r_w)_{w \in V \backslash \{v\}}}$ will lead to a hyperbolic circle packing ${\tilde {\mathcal C}}$ with the required properties. There are two obvious constraints that need to be satisfied:

(i) (Local constraint) The angles ${\alpha_1( \tilde r_w, \tilde r_{w_1}, \tilde r_{w_2})}$ of all the hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w,w_1,w_2)}$ around any given interior vertex ${w}$ must sum to exactly ${2\pi}$ . (In particular, this forces ${\tilde r_w}$ to be finite, since otherwise all the angles here would vanish.)
(ii) (Boundary constraint) The radii associated to boundary vertices must be infinite.

There could potentially also be a global constraint, in that one requires the circles of the packing to be disjoint – including circles that are not necessarily adjacent to each other. In general, one can easily create configurations of circles that are local circle packings but not global ones (see e.g., Figure 7 of Beardon-Stephenson). However, it turns out that one can use the boundary constraint and topological arguments to prevent this from happening. We first need a topological lemma:

Lemma 16 (Topological lemma) Let ${U, V}$ be bounded connected open subsets of ${{\bf C}}$ with ${V}$ simply connected, and let ${f: \overline{U} \rightarrow \overline{V}}$ be a continuous map such that ${f(\partial U) \subset \partial V}$ and ${f(U) \subset V}$ . Suppose furthermore that the restriction of ${f}$ to ${U}$ is a local homeomorphism. Then ${f}$ is in fact a global homeomorphism from ${U}$ to ${V}$ .

The requirement that the restriction of ${f}$ to ${U}$ be a local homeomorphism can in fact be relaxed to local injectivity thanks to the invariance of domain theorem. The complex numbers ${{\bf C}}$ can be replaced here by any finite-dimensional manifold.

Proof: The preimage ${f^{-1}(p)}$ of any point ${p}$ in the interior of ${V}$ is closed, discrete, and disjoint from ${\partial U}$ , and is hence finite. Around each point in the preimage, there is a neighbourhood on which ${f}$ is a homeomorphism onto a neighbourhood of ${p}$ . If one deletes the closure of these neighbourhoods, the image under ${f}$ is compact and avoids ${p}$ , and thus avoids a neighbourhood of ${p}$ . From this we can show that ${f}$ is a covering map from ${U}$ to ${V}$ . As the base ${V}$ is simply connected, it is its own universal cover, and hence (by the connectedness of ${U}$ ) ${f}$ must be a homeomorphism as claimed. $\Box$

Proposition 17 Suppose we assign a radius ${\tilde r_w \in (0,+\infty]}$ to each ${w \in V \backslash \{v\}}$ that obeys the local constraint (i) and the boundary constraint (ii). Then there is a hyperbolic circle packing ${(C(\tilde p_w, \tilde r_w))_{w \in V \backslash \{v\}}}$ with nerve ${G - \{v\}}$ and the indicated radii.

Proof: We first create the hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ associated with the required hyperbolic circle packing, and then verify that this indeed arises from a circle packing.

Start with a single triangle ${(w^0_1,w^0_2,w^0_3)}$ in ${G - \{v\}}$ , and arbitrarily select a ${(\tilde r_{w^0_1}, \tilde r_{w^0_2}, \tilde r_{w^0_3})}$ -triangle ${\Delta_{\tilde {\mathcal C}}(w^0_1,w^0_2,w^0_3)}$ with the same orientation as ${\Delta_{{\mathcal C}}(w_1,w_2,w_3)}$ . By Exercise 15(i), such a triangle exists (and is unique up to Möbius automorphisms of the disk). If a hyperbolic triangle ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ has been fixed, and ${(w_2,w_3,w_4)}$ (say) is an adjacent triangle in ${G - \{v\}}$ , we can select ${\Delta_{\tilde {\mathcal C}}(w_2,w_3,w_4)}$ to be the unique ${(r_{w_2}, r_{w_3}, r_{w_4})}$ -triangle with the same orientation as ${\Delta_{{\mathcal C}}(w_2,w_3,w_4)}$ that shares the ${w_2,w_3}$ side in common with ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ (with the ${w_2}$ and ${w_3}$ vertices agreeing). Similarly for other permutations of the labels. As ${G}$ is a maximal planar graph with ${v}$ non-degenerate (so in particular the set of internal vertices is connected), we can continue this construction to eventually fix every triangle in ${G - \{v\}}$ . There is the potential issue that a given triangle ${\Delta_{{\mathcal C}}(w_1,w_2,w_3)}$ may depend on the order in which one arrives at that triangle starting from ${(w^0_1,w^0_2,w^0_3)}$ , but one can check from a monodromy argument (in the spirit of the monodromy theorem) using the local constraint (i) and the simply connected nature of the triangulation associated to ${{\mathcal C}}$ that there is in fact no dependence on the order. (The process resembles that of laying down jigsaw pieces in the shape of hyperbolic triangles together, with the local constraint ensuring that there is always a flush fit locally.)

Now we show that the hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ have disjoint interiors inside the disk ${D(0,1)}$ . Let ${X}$ denote the topological space formed by taking the disjoint union of the hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ (now viewed as abstract topological spaces rather than subsets of the disk) and then gluing together all common edges, e.g. identifying the ${\{w_2,w_3\}}$ edge of ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ with the same edge of ${\Delta_{\tilde {\mathcal C}}(w_2,w_3,w_4)}$ if ${(w_1,w_2,w_3)}$ and ${(w_2,w_3,w_4)}$ are adjacent triangles in ${G - \{v\}}$ . This space is homeomorphic to the union of the original hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ , and is thus homeomorphic to the closed unit disk. There is an obvious projection map ${\pi}$ from ${X}$ to the union of the ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ , which maps the abstract copy in ${X}$ of a given hyperbolic triangle ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ to its concrete counterpart in ${\overline{D(0,1)}}$ in the obvious fashion. This map is continuous. It does not quite cover the full closed disk, mainly because (by the boundary condition (ii)) the boundary hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(v_i,v_{i+1},w)}$ touch the boundary of the disk at the vertices associated to ${v_i}$ and ${v_{i+1}}$ but do not follow the boundary arc connecting these vertices, being bounded instead by the geodesic from the ${v_i}$ vertex to the ${v_{i+1}}$ vertex; the missing region is a lens-shaped region bounded by two circular arcs. However, by applying another homeomorphism (that does not alter the edges from ${v_i}$ to ${w}$ or ${v_{i+1}}$ to ${w}$ ), one can “push out” the ${\{v_i,v_{i+1}\}}$ edge of this hyperbolic triangle across the lens to become the boundary arc from ${v_i}$ to ${v_{i+1}}$ . If one performs this modification for each boundary triangle, one arrives at a modified continuous map ${\tilde \pi}$ from ${X}$ to ${\overline{D(0,1)}}$ , which now has the property that the boundary of ${X}$ maps to the boundary of the disk, and the interior of ${X}$ maps to the interior of the disk. Also one can check that this map is a local homeomorphism. By Lemma 16, ${\tilde \pi}$ is injective. (One can view ${X}$ as a closed and bounded subset of a surface.) Thus the hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ have disjoint interiors, andfor each boundary triangle ${\Delta_{\tilde {\mathcal C}}(v_i,v_{i+1},w)}$ , the lens-shaped regions between the boundary arc between the vertices associated to ${v_i, v_{i+1}}$ and the corresponding edge of the boundary triangle are also disjoint from the hyperbolic triangles and from each other. Each vertex ${w}$ in ${G - \{v\}}$ is associated with a vertex ${\tilde p_w}$ in ${X}$ (or in ${D(0,1)}$ ), and we can associate a unique circle ${C(\tilde p_w,\tilde r_w)}$ with the specified radius which obeys the required tangencies. This is obvious for interior vertices ${w}$ where the radius is finite; for boundary vertices ${w}$ , we see that for every triangle ${ww_1w_2}$ containing ${w}$ there is a unique candidate for the horocycle ${C(\tilde p_w, \infty)}$ that is tangent to the circles from ${w_1,w_2}$ (recall that at least one of ${w_1,w_2}$ must be interior), and by comparing adjacent triangles we see that the associated candidate horocycles must match, so there is a well defined horocycle to attach to each boundary vertex. All of the hyperbolic circles ${C(\tilde p_w, \tilde r_w)}$ and their interiors are contained in the union of the hyperbolic triangles ${\Delta_{\tilde {\mathcal C}}(w_1,w_2,w_3)}$ and the lens-shaped regions, with each hyperbolic triangle containing portions only of the hyperbolic circles with hyperbolic centres at the vertices of the triangle, and similarly for the lens-shaped regions. From this one can verify that the interiors of the hyperbolic circles are all disjoint from each other, and give a hyperbolic circle packing with the required properties. $\Box$

In view of the above proposition, the only remaining task is to find an assignment of radii ${(\tilde r_w)_{w \in V \backslash \{v\}}}$ obeying both the local condition (i) and the boundary condition (ii). This is analogous to finding a harmonic function with specified boundary data. To do this, we perform the following analogue of Perron’s method. Define a subpacking to be an assignment ${(\tilde r_w)_{w \in V \backslash \{v\}}}$ of radii ${\tilde r_w \in (0,+\infty]}$ obeying the following

(i’) (Local sub-condition) The angles ${\alpha_1( \tilde r_w, \tilde r_{w_1}, \tilde r_{w_2})}$ around any given interior vertex ${w}$ sum to at least ${2\pi}$ .

This can be compared with the definition of a (smooth) subharmonic function as one where the Laplacian is always at least zero. Note that we always have at least one subpacking, namely the one provided by the radii of the original hyperbolic circle packing ${{\mathcal C}}$ . Intuitively, in each subpacking, the radius ${\tilde r_w}$ at an interior vertex ${w}$ is either “too small” or “just right”.
We now need a key monotonicity property, analogous to how the maximum of two subharmonic functions is again subharmonic:

Exercise 18 (Monotonicity)

(i) Show that the angle ${\alpha_1( r_1, r_2, r_3)}$ (as defined in Exercise 15(i)) is strictly decreasing in ${r_1}$ and (when ${r_1}$ is finite) strictly increasing in ${r_2}$ or ${r_3}$ (if one holds the other two radii fixed). Do these claims agree with your geometric intuition?

(ii) Conclude that whenever ${{\mathcal R}' = (r'_w)_{w \in V \backslash \{v\}}}$ and ${{\mathcal R}'' = (r''_w)_{w \in V \backslash \{v\}}}$ are subpackings, that ${\max( {\mathcal R}' , {\mathcal R}'' ) := (\max(r'_w, r''_w))_{w \in V \backslash \{v\}}}$ is also a subpacking.

(iii) Let ${(r_1,r_2,r_3), (r'_1,r'_2,r'_3) \in T}$ be such that ${r_i \leq r'_i}$ for ${i=1,2,3}$ . Show that ${\mathrm{Area}(r_1,r_2,r_3) \leq \mathrm{Area}(r'_1,r'_2,r'_3)}$ , with equality if and only if ${r_i=r'_i}$ for all ${i=1,2,3}$ . (Hint: increase just one of the radii ${r_1,r_2,r_3}$ . One can either use calculus (after first disposing of various infinite radii cases) or one can argue geometrically.)

As with Perron’s method, we can now try to construct a hyperbolic circle packing by taking the supremum of all the subpackings. To avoid degeneracies we need an upper bound:

Proposition 19 (Upper bound) Let ${(\tilde r_w)_{w \in V \backslash \{v\}}}$ be a subpacking. Then for any interior vertex ${w}$ of degree ${d}$ , one has ${\tilde r_w \leq \sqrt{d}}$ .

The precise value of ${\sqrt{d}}$ is not so important for our arguments, but the fact that it is finite will be. This boundedness of interior circles in a circle packing is a key feature of hyperbolic geometry that is not present in Euclidean geometry, and is one of the reasons why we moved to a hyperbolic perspective in the first place.

Proof: By the subpacking property and pigeonhole principle, there is a triangle ${w, w_1, w_2}$ in ${G - \{v\}}$ such that ${\alpha_1(w,w_1,w_2) \geq \frac{2\pi}{d}}$ . The hyperbolic triangle associated to ${(w_1,w_2,w_3)}$ has area at most ${\pi}$ by (2); on the other hand, it contains a sector of a hyperbolic circle of radius ${\tilde r_w}$ and angle ${\frac{2\pi}{d}}$ , and hence has area at least ${\frac{1}{d} 4\pi \sinh^2(r/2) \geq \frac{\pi r^2}{d}}$ , thanks to Exercise 15(iv). Comparing the two bounds gives the claim. $\Box$

Now define ${{\mathcal R} = ( \tilde r_w )_{w \in V \backslash \{v\}}}$ to be the (pointwise) supremum of all the subpackings. By the above proposition, ${\tilde r_w}$ is finite at every interior vertex. By Exercise 18, one can view ${{\mathcal R}}$ as a monotone increasing limit of subpackings, and is thus again a subpacking (due to the continuity properties of ${\alpha_1}$ as long as at least one of the radii stays bounded); thus ${{\mathcal R}}$ is the maximal subpacking. On the other hand, if ${\tilde r_w}$ is finite at some boundary vertex, then by Exercise 18(i) one could replace that radius by a larger quantity without destroying the subpacking property, contradicting the maximality of ${{\mathcal R}}$ . Thus all the boundary radii are infinite, that is to say the boundary condition (ii) holds. Finally, if the sum of the angles at an interior vertex ${w}$ is strictly greater than ${\pi}$ , then by Exercise 18 we could increase the radius at this vertex slightly without destroying the subpacking property at ${w}$ or at any other of the interior vertices, again contradicting the maximality of ${{\mathcal R}}$ . Thus ${{\mathcal R}}$ obeys the local condition (i), and we have demonstrated existence of the required hyperbolic circle packing.

Finally we establish uniqueness. It suffices to establish that ${{\mathcal R}}$ is the unique tuple that obeys the local condition (i) and the boundary condition (ii). Suppose we had another tuple ${{\mathcal R}' = ( r'_w )_{w \in V \backslash \{v\}}}$ other than ${{\mathcal R}}$ that obeyed these two conditions. Then by the maximality of ${{\mathcal R}}$ , we have ${r'_w \leq \tilde r_w}$ for all ${w}$ . By Exercise 18(iii), this implies that

$\displaystyle \mathrm{Area}( r'_{w_1}, r'_{w_2}, r'_{w_3} ) \leq \mathrm{Area}( \tilde r_{w_1}, \tilde r_{w_2}, \tilde r_{w_3} )$

for any triangle ${(w_1,w_2,w_3)}$ in ${T}$ . Summing over all triangles and using (2), we conclude that

$\displaystyle \sum_{w \in V \backslash \{v\}} \sum_{w_1,w_2: (w,w_1,w_2) \hbox{ triangle}} \alpha_1(r'_{w}, r'_{w_1}, r'_{w_2})$

$\displaystyle \geq \sum_{w \in V \backslash \{v\}} \sum_{w_1,w_2: (w,w_1,w_2) \hbox{ triangle}} \alpha_1(\tilde r_{w}, \tilde r_{w_1}, \tilde r_{w_2})$

where the inner sum is over the pairs ${w_1,w_2}$ such that ${(w,w_1,w_2)}$ forms a triangle in ${G - \{v\}}$ . But by the local condition (i) and the boundary condition (ii), the inner sum on either side is equal to ${2\pi}$ for an interior vertex and ${0}$ for a boundary vertex. Thus the two sides agree, which by Exercise 18(iii) implies that ${r'_w = \tilde r_w}$ for all ${w}$ . This proves Theorem 14 and thus Theorems 7, 3, 4.

— 2. Quasiconformal maps —

In this section we set up some of the foundational theory of quasiconformal mapping, which are generalisations of the conformal mapping concept that can tolerate some deviations from perfect conformality, while still retaining many of the good properties of conformal maps (such as being preserved under uniform limits), though with the notable caveat that in contrast to conformal maps, quasiconformal maps need not be smooth. As such, this theory will come in handy when proving convergence of circle packings to the Riemann map. The material here is largely drawn from the text of Lehto and Virtanen.

We first need the following refinement of the Riemann mapping theorem, known as Carathéodory’s theorem:

Theorem 20 (Carathéodory’s theorem) Let ${U}$ be a bounded simply connected domain in ${{\bf C}}$ whose boundary ${\partial U}$ is a Jordan curve, and let ${\phi: D(0,1) \rightarrow U}$ be a conformal map between ${D(0,1)}$ and ${U}$ (as given by the Riemann mapping theorem). Then ${\phi}$ extends to a continuous homeomorphism from ${\overline{D}(0,1)}$ to ${\overline{U}}$ .

The condition that ${\partial U}$ be a Jordan curve is clearly necessary, since if ${\partial U}$ is not simple then there are paths in ${D(0,1)}$ that end up at different points in ${\partial D(0,1)}$ but have the same endpoint in ${\partial U}$ after applying ${\phi}$ , which prevents ${\phi}$ being continuously extended to a homeomorphism. If one relaxes the requirement that ${\partial U}$ be a Jordan curve to the claim that ${{\bf C} \backslash U}$ is locally connected, then it is possible to modify this argument to still obtain a continuous extension of ${U}$ to ${\overline{U}}$ , although the extension will no longer be necessarily a homeomorphism, but we will not prove this fact here. We remark that Carathéodory’s theorem immediately implies as a corollary the Jordan-Schoenflies theorem that the closed region enclosed by a Jordan curve is homeomorphic to the closed unit disk (with the interior being mapped to the interior, and similarly for the boundary).

Proof: We first prove continuous extension to the boundary. It suffices to show that for every point ${\zeta}$ on the boundary of the unit circle, the diameters of the sets ${\phi( D(0,1) \cap D( \zeta, r_n ) )}$ go to zero for some sequence of radii ${r_n \rightarrow 0}$ .

First observe from the change of variables formula that the area of ${U = \phi(D(0,1))}$ is given by ${\int_{D(0,1)} |\phi'(z)|^2\ dx dy}$ , where ${dx dy}$ denotes Lebesgue measure (or the area element). In particular, this integral is finite. Expanding in polar coordinates around ${\zeta}$ , we conclude that

$\displaystyle \int_0^2 \left(\int_{0}^{2\pi} 1_{D(0,1)}(\zeta+re^{i\theta}) |\phi'( \zeta + r e^{i\theta} )|^2\ d \theta\right) r dr < \infty.$

Since ${\int_0^2 \frac{dr}{r}}$ diverges near ${r=0}$ , we conclude from the pigeonhole principle that there exists a sequence of radii ${0 < r_n < 2}$ decreasing to zero such that

$\displaystyle r_n^2 \int_{0}^{2\pi} 1_{D(0,1)}(\zeta+r_ne^{i\theta}) |\phi'( \zeta + r_n e^{i\theta} )|^2\ d \theta \rightarrow 0$

and hence by Cauchy-Schwarz

$\displaystyle r_n \int_{0}^{2\pi} 1_{D(0,1)}(\zeta+r_ne^{i\theta}) |\phi'( \zeta + r_n e^{i\theta} )|\ d \theta \rightarrow 0$

If we let ${C_n}$ denote the circular arc ${\{ \zeta + r_n e^{i\theta}: 0 \leq \theta \leq 2\pi \} \cap D(0,1)}$ , we conclude from this and the triangle inequality (and chain rule) that ${\phi(C_n)}$ is a rectifiable curve with length going to zero as ${n \rightarrow \infty}$ . Let ${a_n, b_n}$ denote the endpoints of this curve. Clearly they lie in ${\overline{U}}$ . If (say) ${a_n}$ was in ${U}$ , then as ${\phi}$ is a homeomorphism from ${D(0,1)}$ to ${U}$ , ${C_n}$ would have one endpoint in ${D(0,1)}$ rather than ${\partial D(0,1)}$ , which is absurd. Thus ${a_n}$ lies in ${\partial U}$ , and similarly for ${b_n}$ . Since the length of ${\phi(C_n)}$ goes to zero, the distance between ${a_n}$ and ${b_n}$ goes to zero. Since ${\partial U}$ is a Jordan curve, it can be parameterised homeomorphically by ${\partial D(0,1)}$ , and so by compactness we also see that the distance between the parameterisations of ${a_n}$ and ${b_n}$ in ${\partial D(0,1)}$ must also go to zero, hence (by uniform continuity of the inverse parameterisation) ${a_n}$ and ${b_n}$ are connected along ${\partial U}$ by an arc whose diameter goes to zero. Combining this arc with ${\phi(C_n)}$ , we obtain a Jordan curve of diameter going to zero which separates ${\phi(D(0,1) \cap D(\zeta, r_n))}$ from the rest of ${U}$ . Sending ${n}$ to infinity, we see that ${\phi(D(0,1) \cap D(\zeta, r_n))}$ (which decreases with ${n}$ ) must eventually map in the interior of this curve rather than the exterior, and so the diameter goes to zero as claimed.
The above construction shows that ${\phi}$ extends to a continuous map (which by abuse of notation we continue to call ${\phi}$ ) from ${\overline{D(0,1)}}$ to ${\overline{U}}$ , and the proof also shows that ${\partial D(0,1)}$ maps to ${\partial U}$ . As ${\phi(\overline{D(0,1)})}$ is a compact subset of ${\overline{U}}$ that contains ${U}$ , it must surject onto ${\overline{U}}$ . As both ${\overline{D(0,1)}}$ and ${\overline{U}}$ are compact Hausdorff spaces, we will now be done if we can show injectivity. The only way injectivity can fail is if there are two distinct points ${\zeta,\omega}$ on ${\partial D(0,1)}$ that map to the same point. Let ${C}$ be the line segment connecting ${\zeta}$ with ${\omega}$ , then ${\phi(C)}$ is a Jordan curve in ${\overline{U}}$ that meets ${\partial U}$ only at ${\phi(\zeta) = \phi(\omega)}$ . ${C}$ divides ${\overline{D(0,1)}}$ into two regions; one of which must map to the interior of ${\phi(C)}$ , which implies that there is an entire arc of ${\partial D(0,1)}$ which maps to the single point ${\phi(\zeta)=\phi(\omega)}$ . But then by the Schwarz reflection principle, ${\phi}$ extends conformally across this arc and is constant in a non-isolated set, thus is constant everywhere by analytic continuation, which is absurd. This establishes the required injectivity. $\Box$

This has the following consequence. Define a Jordan quadrilateral to be the open region ${Q}$ enclosed by a Jordan curve with four distinct marked points ${p_1,p_2,p_3,p_4}$ on it in counterclockwise order, which we call the vertices of the quadrilateral. The arcs in ${\partial Q}$ connecting ${p_1}$ to ${p_2}$ or ${p_3}$ to ${p_4}$ will be called the ${a}$ -sides; the arcs connecting ${p_2}$ to ${p_3}$ or ${p_4}$ to ${p_1}$ will be called ${b}$ -sides. (Thus for instance each cyclic permutation of the ${p_1,p_2,p_3,p_4}$ vertices will swap the ${a}$ -sides and ${b}$ -sides, while keeping the interior region ${Q}$ unchanged.) A key example of a Jordan quadrilateral are the (Euclidean) rectangles, in which the vertices ${p_1,\dots,p_4}$ are the usual corners of the rectangle, traversed counterclockwise. The ${a}$ -sides then are line segments of some length ${a}$ , and the ${b}$ -sides are line segments of some length ${b}$ that are orthogonal to the ${a}$ -sides. A vertex-preserving conformal map from one Jordan quadrilateral ${Q}$ to another ${Q'}$ will be a conformal map that extends to a homeomorphism from ${\overline{Q}}$ to ${\overline{Q'}}$ that maps the corners of ${Q}$ to the respective corners of ${Q'}$ (in particular, ${a}$ -sides get mapped to ${a}$ -sides, and similarly for ${b}$ -sides).

Exercise 21 Let ${Q}$ be a Jordan quadrilateral with vertices ${p_1,p_2,p_3,p_4}$ .

(i) Show that there exists ${r > 1}$ and a conformal map ${\phi: Q \rightarrow \mathbf{H}}$ to the upper half-plane ${\mathbf{H} := \{ z: \mathrm{Im} z > 0 \}}$ (viewed as a subset of the Riemann sphere) that extends continuously to a homeomorphism ${\phi: \overline{Q} \rightarrow \overline{\mathbf{H}}}$ and which maps ${p_1,p_2,p_3,p_4}$ to ${-r, -1, 1, r}$ respectively. (Hint: first map ${p_1,p_2,p_3,p_4}$ to increasing elements of the real line, then use the intermediate value theorem to enforce ${\phi(p_1)+\phi(p_4) = \phi(p_2)+\phi(p_3)}$ .)

(ii) Show that there is a vertex-preserving conformal map ${\psi: Q \rightarrow R}$ from ${Q}$ to a rectangle ${R}$ . (Hint: use Schwarz-Christoffel mapping.)

(iii) Show that the rectangle ${R}$ in part (ii) is unique up to affine transformations. (Hint: if one has a conformal map between rectangles that preserves the vertices, extend it via repeated use of the Schwarz reflection principle to an entire map.)

This allows for the following definition: the conformal modulus ${\mathrm{mod}(Q)}$ (or modulus for short, also called module in older literature) of a Jordan quadrilateral with vertices ${p_1,p_2,p_3,p_4}$ is the ratio ${b/a}$ , where ${a,b}$ are the lengths of the ${a}$ -sides and ${b}$ -sides of a rectangle ${R}$ that is conformal to ${Q}$ in a vertex-preserving vashion.. This is a number between ${0}$ and ${\infty}$ ; each cyclic permutation of the vertices replaces the modulus with its reciprocal. It is clear from construction that the modulus of a Jordan quadrilateral is unaffected by vertex-preserving conformal transformations.

Now we define quasiconformal maps. Informally, conformal maps are homeomorphisms that map infinitesimal circles to infinitesimal circles; quasiconformal maps are homeomorphisms that map infinitesimal circles to curves that differ from an infinitesimal circle by “bounded distortion”. However, for the purpose of setting up the foundations of the theory, it is slightly more convenient to work with rectangles instead of circles (it is easier to partition rectangles into subrectangles than disks into subdisks). We therefore introduce

Definition 22 Let ${K \geq 1}$ . An orientation-preserving homeomorphism ${\phi: U \rightarrow V}$ between two domains ${U,V}$ in ${{\bf C}}$ is said to be ${K}$ -quasiconformal if one has ${\mathrm{mod}(\phi(Q)) \leq K \mathrm{mod}(Q)}$ for every Jordan quadrilateral ${Q}$ in ${U}$ . (In these notes, we do not consider orientation-reversing homeomorphisms to be quasiconformal.)

Note that by cyclically permuting the vertices of ${Q}$ , we automatically also obtain the inequality

$\displaystyle \frac{1}{\mathrm{mod}(\phi(Q))} \leq K \frac{1}{\mathrm{mod}(Q)}$

or equivalently

$\displaystyle \frac{1}{K} \mathrm{mod}(Q) \leq \mathrm{mod}(\phi(Q))$

for any Jordan quadrilateral. Thus it is not possible to have any ${K}$ -quasiconformal maps for ${K<1}$ (excluding the degenerate case when ${U,V}$ are empty), and a map is ${1}$ -quasiconformal if and only if it preserves the modulus. In particular, conformal maps are ${1}$ -quasiconformal; we will shortly establish that the converse claim is also true. It is also clear from the definition that the inverse of a ${K}$ -quasiconformal map is also ${K}$ -quasiconformal, and the composition of a ${K}$ -quasiconformal map and a ${K'}$ -quasiconformal map is a ${KK'}$ -quasiconformal map.
It is helpful to have an alternate characterisation of the modulus that does not explicitly mention conformal mapping:

Proposition 23 (Alternate definition of modulus) Let ${Q}$ be a Jordan quadrilateral with vertices ${p_1,p_2,p_3,p_4}$ . Then ${\mathrm{mod}(Q)}$ is the smallest quantity with the following property: for any Borel measurable ${\rho: Q \rightarrow [0,+\infty)}$ one can find a curve ${\gamma}$ in ${Q}$ connecting one ${a}$ -side of ${Q}$ to another, and which is locally rectifiable away from endpoints, such that

$\displaystyle \left(\int_\gamma \rho(z)\ |dz|\right)^2 \leq \mathrm{mod}(Q) \int_Q \rho^2(z)\ dx dy$

where ${\int_\gamma |dz|}$ denotes integration using the length element of ${\gamma}$ (not to be confused with the contour integral ${\int_\gamma\ dz}$ ).

The reciprocal of this notion of modulus generalises to the concept of extremal length, which we will not develop further here.

Proof: Observe from the change of variables formula that if ${\phi: Q \rightarrow Q'}$ is a vertex-preserving conformal mapping between Jordan quadrilaterals ${Q,Q'}$ , and ${\gamma}$ is a locally rectifiable curve connecting one ${a}$ -side of ${Q}$ to another, then ${\phi \circ \gamma}$ is a locally rectifiable curve connecting one ${a}$ -side of ${Q'}$ to another, with

$\displaystyle \int_{\phi \circ \gamma} \rho \circ \phi^{-1}(w) \ |dw| = \int_\gamma \rho(z) |\phi'(z)|\ |dz|$

and

$\displaystyle \int_{Q'} |\rho \circ \phi^{-1}(w)|^2\ dx dy = \int_Q |\rho(z)|^2 |\phi'(z)|^2\ dx dy.$

As a consequence, if the proposition holds for ${Q}$ it also holds for ${Q'}$ . Thus we may assume without loss of generality that ${Q}$ is a rectangle, which we may normalise to be ${\{ x+iy: 0 \leq y \leq 1; 0 \leq x \leq M \}}$ with vertices ${i, 0, M, M+i}$ , so that the modulus is ${M}$ . For any measurable ${\rho: Q \rightarrow [0,+\infty)}$ , we have from Cauchy-Schwarz and Fubini’s theorem that

$\displaystyle \int_0^1 \left(\int_0^M \rho(x+iy)\ dx\right)^2 dy \leq M \int_0^1 \int_0^M \rho^2(x+iy)\ dx dy$

$\displaystyle = M \int_Q \rho^2(z)\ dx dy$

and hence by the pigeonhole principle there exists ${y}$ such that

$\displaystyle \left(\int_0^M \rho(x+iy)\ dx\right)^2 \leq M \int_Q \rho^2(z)\ dx dy.$

On the other hand, if we set ${\rho=1}$ , then ${\int_Q \rho^2(z)\ dx dy = M}$ , and for any curve ${\gamma}$ connecting the ${a}$ -side from ${0}$ to ${i}$ to the ${a}$ -side from ${M}$ to ${M+i}$ , we have

$\displaystyle \int_\gamma \rho\ |dz| \geq \left| \int_\gamma \rho\ dx \right| = M.$

Thus ${M}$ is the best constant with the required property, proving the claim. $\Box$
Here are some quick and useful consequences of this characterisation:

Exercise 24 (Rengel’s inequality) Let ${Q}$ be a Jordan quadrilateral of area ${A}$ , let ${b}$ be the shortest (Euclidean) distance between a point on one ${a}$ -side and a point on the other ${a}$ -side, and similarly let ${a}$ be the shortest (Euclidean) distance between a point on one ${b}$ -side and a point on the other ${b}$ -side. Show that

$\displaystyle \frac{b^2}{A} \leq \mathrm{mod}(Q) \leq \frac{A}{a^2}$

and that equality in either case occurs if and only if ${Q}$ is a rectangle. (Hint: for the equality case, conformally map ${Q}$ back to a rectangle and use the change of variables analysis used to prove Proposition 23.)

Exercise 25 (Superadditivity)

(i) If ${Q_1, Q_2}$ are disjoint Jordan quadrilaterals that share a common ${a}$ -side, and which can be glued together along this side to form a new Jordan quadrilateral ${Q_1 \cup Q_2}$ , show that ${\mathrm{mod}(Q_1 \cup Q_2) \geq \mathrm{mod}(Q_1) + \mathrm{mod}(Q_2)}$ . If equality occurs, show that after conformally mapping ${Q_1 \cup Q_2}$ to a rectangle (in a vertex preserving fashion), ${Q_1}$ , ${Q_2}$ are mapped to subrectangles (formed by cutting the original parallel to the ${a}$ -side).

(ii) If ${Q_1, Q_2}$ are disjoint Jordan quadrilaterals that share a common ${b}$ -side, and which can be glued together along this side to form a new Jordan quadrilateral ${Q_1 \cup Q_2}$ , show that ${\frac{1}{\mathrm{mod}(Q_1 \cup Q_2)} \geq \frac{1}{\mathrm{mod}(Q_1)} + \frac{1}{\mathrm{mod}(Q_2)}}$ . If equality occurs, show that after conformally mapping ${Q_1 \cup Q_2}$ to a rectangle (in a vertex preserving fashion), ${Q_1}$ , ${Q_2}$ are mapped to subrectangles (formed by cutting the original parallel to the ${b}$ -side).

Exercise 26 (Continuity from below) Suppose ${Q_n}$ is a sequence of Jordan quadrilaterals which converge to another Jordan quadrilateral ${Q}$ , in the sense that the vertices of ${Q_n}$ converge to their respective counterparts in ${Q}$ , each ${a}$ -side in ${Q_n}$ converges (in the Hausdorff sense) to the ${a}$ -side of ${Q}$ , and the similarly for ${b}$ -sides. Suppose also that ${Q_n \subset Q}$ for all ${n}$ . Show that ${\mathrm{mod}(Q_n)}$ converges to ${\mathrm{mod}(Q)}$ . (Hint: map ${Q}$ to a rectangle and use Rengel’s inequality.)

Proposition 27 (Local quasiconformality implies quasiconformality) Let ${K \geq 1}$ , and let ${\phi: U \rightarrow V}$ be an orientation-preserving homeomorphism between complex domains ${U,V}$ which is locally ${K}$ -quasiconformal in the sense that for every ${z_0 \in U}$ there is a neighbourhood ${U_{z_0}}$ of ${z_0}$ in ${U}$ such that ${\phi}$ is ${K}$ -quasiconformal from ${U_{z_0}}$ to ${\phi(U_{z_0})}$ . Then ${\phi}$ is ${K}$ -quasiconformal.

Proof: We need to show that ${\mathrm{mod}(\phi(Q)) \leq K \mathrm{mod}(Q)}$ for any Jordan quadrilateral ${Q}$ in ${U}$ . The hypothesis gives this claim for all quadrilaterals in the sufficiently small neighbourhood of any point in ${U}$ . For any natural number ${n}$ , we can subdivide ${\phi(Q)}$ into ${n}$ quadrilaterals ${\phi(Q_1),\dots,\phi(Q_n)}$ with modulus ${\frac{1}{n} \mathrm{mod}(\phi(Q))}$ with adjacent ${a}$ -sides, by first conformally mapping ${\phi(Q)}$ to a rectangle and then doing an equally spaced vertical subdivision. Similarly, each quadrilateral ${Q_i}$ can be subdivided into ${n}$ quadrilaterals ${Q_{i,1},\dots,Q_{i,n}}$ of modulus ${n \mathrm{mod}(Q_i)}$ by mapping ${Q_i}$ to a rectangle and performing horizontal subdivision. By the local ${K}$ -quasiconformality of ${\phi}$ , we will have

$\displaystyle \mathrm{mod}( \phi(Q_{i,j}) ) \leq K \mathrm{mod}( Q_{i,j} ) = K n \mathrm{mod}(Q_i)$

for all ${i,j=1,\dots,n}$ , if ${n}$ is large enough. By superadditivity this implies that

$\displaystyle \mathrm{mod}( \phi(Q_i) ) \leq K\mathrm{mod}(Q_i)$

for each ${i}$ , and hence

$\displaystyle \mathrm{mod}(Q_i) \geq \frac{1}{Kn} \mathrm{mod}(\phi(Q)).$

Applying superadditivity again we obtain

$\displaystyle \mathrm{mod}(Q) \geq \frac{1}{K} \mathrm{mod}(\phi(Q)).$

giving the claim. $\Box$
We can now reverse the implication that conformal maps are ${1}$ -quasiconformal:

Proposition 28 Every ${1}$ -quasiconformal map ${\phi: U \rightarrow V}$ is conformal.

Proof: By covering ${U}$ by quadrilaterals we may assume without loss of generality that ${U}$ (and hence also ${\phi(U)=V}$ ) is a Jordan quadrilateral; by composing on left and right with conformal maps we may assume that ${U}$ and ${V}$ are rectangles. As ${\phi}$ is ${1}$ -quasiconformal, the rectangles have the same modulus, so after a further affine transformation we may assume that ${U=V}$ is the rectangle with vertices ${i, 0, M, M+i}$ for some modulus ${M}$ . If one subdivides ${U}$ into two rectangles along an intermediate vertical line segment connecting say ${x}$ to ${x+i}$ for some ${0 < x < M}$ , the moduli of these rectangles are ${x}$ and ${M-x}$ . Applying the ${1}$ -quasiconformal map and the converse portion of Exercise 25, we conclude that these rectangles must be preserved by ${\phi}$ , thus ${\phi}$ preserves the ${x}$ coordinate. Similarly ${\phi}$ preserves the ${y}$ coordinate, and is therefore the identity map, which is of course conformal. $\Box$

Next, we can give a simple criterion for quasiconformality in the continuously differentiable case:

Theorem 29 Let ${K \geq 1}$ , and let ${\phi: U \rightarrow V}$ be an orientation-preserving diffeomorphism (a continuously (real) differentiable homeomorphism whose derivative is always nondegenerate) between complex domains ${U,V}$ . Then the following are equivalent:

(i) ${\phi}$ is ${K}$ -quasiconformal.

(ii) For any point ${z_0 \in U}$ and phases ${v,w \in S^1 := \{ z \in {\bf C}: |z|=1\}}$ , one has
$\displaystyle |D_v \phi(z_0)| \leq K|D_w \phi(z_0)|$

where ${D_v \phi(z_0) := \frac{\partial}{\partial t} \phi(z_0+tv)|_{t=0}}$ denotes the directional derivative.

Proof: Let us first show that (ii) implies (i). Let ${Q}$ be a Jordan quadrilateral in ${U}$ ; we have to show that ${\mathrm{mod}(\phi(Q)) \leq K \mathrm{mod}(Q)}$ . From the chain rule one can check that condition (ii) is unchanged by composing ${\phi}$ with conformal maps on the left or right, so we may assume without loss of generality that ${Q}$ and ${\phi(Q)}$ are rectangles; in fact we may normalise ${Q}$ to have vertices ${i, 0, T, T+i}$ and ${\phi(Q)}$ to have vertices ${i, 0, T', T'+i}$ where ${T = \mathrm{mod}(Q)}$ and ${T' = \mathrm{mod}(Q')}$ . From the change of variables formula (and the singular value decomposition), followed by Fubini’s theorem and Cauchy-Schwarz, we have

$\displaystyle T' = \int_{\phi(Q)}\ dx dy$

$\displaystyle = \int_Q \mathrm{det}(D\phi)(z)\ dx dy$

$\displaystyle = \int_Q \max_{v \in S^1} |D_v \phi(z)| \min_{w \in S^1} |D_w \phi(z)|\ dx dy$

$\displaystyle \geq \int_Q \frac{1}{K} \left|\frac{\partial}{\partial x} \phi(z)\right|^2\ dx dy$

$\displaystyle = \frac{1}{K} \int_0^1 \int_0^T \left|\frac{\partial}{\partial x} \phi(x+iy)\right|^2\ dx dy$

$\displaystyle \geq \frac{1}{K T} \int_0^1 \left|\int_0^T \frac{\partial}{\partial x} \mathrm{Re} \phi(x+iy)\ dx\right|^2\ dy$

$\displaystyle = \frac{1}{K T} \int_0^1 (T')^2\ dy$

and hence ${T' \leq K T}$ , giving the claim.
Now suppose that (ii) failed, then by the singular value decomposition we can find ${z_0 \in U}$ and a phase ${v \in S^1}$ such that

$\displaystyle D_{iv} \phi(z_0) = i \lambda D_v \phi(z_0)$

for some real ${\lambda}$ with ${\lambda > K}$ . After translations and rotations we may normalise so that

$\displaystyle \phi(0) = 0; \frac{\partial}{\partial x} \phi(0) = 1; \frac{\partial}{\partial y} \phi(0) = i\lambda.$

But then from Rengel’s inequality and Taylor expansion one sees that ${\phi}$ will map a unit square with vertices ${0, -\varepsilon, -\varepsilon+i\varepsilon, i\varepsilon}$ to a quadrilateral of modulus converging to ${\lambda}$ as ${\varepsilon \rightarrow 0}$ , contradicting (i). $\Box$

Exercise 30 Show that the conditions (i), (ii) in the above theorem are also equivalent to the bound

$\displaystyle \left|\frac{\partial}{\partial \overline{z}} \phi(z_0)\right| \leq \frac{K-1}{K+1} \left|\frac{\partial }{\partial z} \phi(z_0)\right|$

for all ${z_0 \in U}$ , where

$\displaystyle \frac{\partial }{\partial z} := \frac{1}{2} ( \frac{\partial }{\partial x} - i \frac{\partial }{\partial y}); \quad \frac{\partial }{\partial \overline{z}} := \frac{1}{2} ( \frac{\partial }{\partial x} + i \frac{\partial }{\partial y})$

are the Wirtinger derivatives.

We now prove a technical regularity result on quasiconformal maps.

Proposition 31 (Absolute continuity on lines) Let ${\phi: U \rightarrow V}$ be a ${K}$ -quasiconformal map between two complex domains ${U,V}$ for some ${K}$ . Suppose that ${U}$ contains the closed rectangle with endpoints ${0, i, T+i, T}$ . Then for almost every ${0 \leq y \leq 1}$ , the map ${x \mapsto \phi(x+iy)}$ is absolutely continuous on ${[0,T]}$ .

Proof: For each ${y}$ , let ${A(y)}$ denote the area of the image ${\{ \phi(x+iy'): 0 \leq x \leq T; 0 \leq y \leq y'\}}$ of the rectangle with endpoints ${0, iy, T+iy, T}$ . This is a bounded monotone function on ${[0,1]}$ and is hence differentiable almost everywhere. It will thus suffice to show that the map ${x \mapsto \phi(x+iy)}$ is absolutely continuous on ${[0,T]}$ whenever ${y \in (0,1)}$ is a point of differentiability of ${A}$ .

Let ${\varepsilon > 0}$ , and let ${[x_1,x'_1],\dots,[x_m,x'_m]}$ be disjoint intervals in ${[0,T]}$ of total length ${\sum_{j=1}^m x'_j-x_j \leq \varepsilon}$ . To show absolute continuity, we need a bound on ${\sum_{j=1}^m |\phi(x'_j) - \phi(x_j)|}$ that goes to zero as ${\varepsilon \rightarrow 0}$ uniformly in the choice of intervals. Let ${\delta>0}$ be a small number (that can depend on the intervals), and for each ${j=1,\dots,m}$ let ${R_j}$ be the rectangle with vertices ${x_j+i(y_j+\delta)}$ , ${x_j+iy}$ , ${x'_j+iy}$ , ${x'_j+i(y+\delta)}$ This rectangle has modulus ${(x'_j-x_j)/\delta}$ , and hence ${\phi(R_j)}$ has modulus at most ${K (x'_j-x_j)/\delta}$ . On the other hand, by Rengel’s inequality this modulus is at least ${|\phi(x'_j)-\phi(x_j)-o(1)|^2 / \mathrm{Area}(\phi(R_j))}$ , where ${o(1)}$ is a quantity that goes to zero as ${\delta \rightarrow 0}$ (holding the intervals fixed). We conclude that

$\displaystyle |\phi(x'_j)-\phi(x_j)|^2 \leq \frac{K}{\delta} (x'_j-x_j) \mathrm{Area}(\phi(R_j)) + o(1).$

On the other hand, we have

$\displaystyle \sum_{j=1}^m \mathrm{Area}(\phi(R_j)) \leq A(y+\delta) - A(y) = (A'(y)+o(1)) \delta.$

By Cauchy-Schwarz, we thus have

$\displaystyle (\sum_{j=1}^m |\phi(x'_j)-\phi(x_j)|)^2 \leq K A'(y) \sum_{j=1}^m (x'_j-x_j) + o(1);$

sending ${\delta \rightarrow 0}$ , we conclude

$\displaystyle \sum_{j=1}^m |\phi(x'_j)-\phi(x_j)| \leq K^{1/2} A'(y)^{1/2} \varepsilon^{1/2}$

giving the claim. $\Box$

Exercise 32 Let ${\phi: U \rightarrow V}$ be a ${K}$ -quasiconformal map between two complex domains ${U,V}$ for some ${K}$ . Suppose that there is a closed set ${S \subset {\bf C}}$ of Lebesgue measure zero such that ${\phi}$ is conformal on ${U \backslash S}$ . Show that ${\phi}$ is ${1}$ -quasiconformal (and hence conformal, by Proposition 28). (Hint: Arguing as in the proof of Theorem 29, it suffices to show that of ${\phi}$ maps the rectangle with endpoints ${0, i, T+i, T}$ to the rectangle with endpoints ${0, i, T'+i, T'}$ , then ${T' \leq T}$ . Repeat the proof of that theorem, using the absolute continuity of lines at a crucial juncture to justify using the fundamental theorem of calculus.)

Recall Hurwitz’s theorem that the locally uniform limit of conformal maps is either conformal or constant. It turns out there is a similar result for quasiconformal maps. We will just prove a weak version of the result (see Theorem II.5.5 of Lehto-Virtanen for the full statement):

Theorem 33 Let ${K \geq 1}$ , and let ${\phi_n: U \rightarrow V_n}$ be a sequence of ${K}$ -quasiconformal maps that converge locally uniformly to an orientation-preserving homeomorphism ${\phi: U \rightarrow V}$ . Then ${\phi}$ is also ${K}$ -quasiconformal.

It is important for this theorem that we do not insist that quasiconformal maps are necessarily differentiable. Indeed for applications to circle packing we will be working with maps that are only piecewise smooth, or possibly even worse, even though at the end of the day we will recover a smooth conformal map in the limit.

Proof: Let ${Q}$ be a Jordan quadrilateral in ${U}$ . We need to show that ${\mathrm{mod}(\phi(Q)) \leq K \mathrm{mod}(Q)}$ . By restricting ${U}$ we may assume ${U=Q}$ . By composing ${\phi, \phi_n}$ with a conformal map we may assume that ${Q}$ is a rectangle. We can write ${Q}$ as the increasing limit of rectangles ${Q_m}$ of the same modulus, then for any ${n,m}$ we have ${\mathrm{mod}(\phi_n(Q_m)) \leq K \mathrm{mod}(Q)}$ . By choosing ${n_m}$ going to infinity sufficiently rapidly, ${\phi_{n_m}(Q_m)}$ stays inside ${\phi(Q)}$ and converges to ${\phi(Q)}$ in the sense of Exercise 26, and the claim then follows from that exercise. $\Box$

Another basic property of conformal mappings (a consequence of Morera’s theorem) is that they can be glued along a common edge as long as the combined map is also a homeomorphism; this fact underlies for instance the Schwarz reflection principle. We have a quasiconformal analogue:

Theorem 34 Let ${K \geq 1}$ , and let ${\phi: U \rightarrow V}$ be an orientation-preserving homeomorphism. Let ${C}$ be a finite union of real analytic (and topologically closed) contours that lie in ${U}$ except possibly at the endpoints. If ${\phi: U \backslash C \rightarrow \phi(U \backslash C)}$ is ${K}$ -quasiconformal, then ${\phi: U \rightarrow V}$ is ${K}$ -quasiconformal.

We will generally apply this theorem in the case when ${C}$ disconnects ${U}$ into two components, in which case ${\phi}$ can be viewed as the gluing of the restrictions of this map to the two components.

Proof: As in the proof of the previous theorem, we may take ${U}$ to be a rectangle ${Q}$ , and it suffices to show that ${\mathrm{mod}(\phi(Q)) \leq K \mathrm{mod}(Q)}$ . We may normalise ${Q}$ to have vertices ${i, 0, M, M+i}$ where ${M = \mathrm{mod}(Q)}$ , and similarly normalise ${\phi(Q)}$ to be a rectangle of vertices ${i, 0, M', M'+i}$ , so we now need to show that ${M' \leq KM}$ . The real analytic contour ${C}$ meets ${Q}$ in a finite number of curves (and points), which can be broken up further into a finite horizontal line segments (and points) and graphs ${\{ f_j(y) + iy: y \in I_j\}}$ for various closed intervals ${I_j \subset [0,1]}$ and continuous ${f_j: I_j \rightarrow [0,M]}$ . For any ${\varepsilon>0}$ , we can then use the uniform continuity of the ${f_j}$ to subdivide ${Q}$ into a finite number of rectangles ${Q_k= \{ x+iy: y \in J_k, 0 \leq x \leq M \}}$ where on each such rectangle, ${C}$ meets the interior of ${Q_k}$ in a bounded number of graphs ${\{ f_j(y) +iy: y \in J_k\}}$ whose horizontal variation is ${O(\varepsilon)}$ . This subdivides ${Q_k}$ into a bounded number of Jordan quadrilaterals ${Q_{k,j}}$ . (Strictly speaking, some of these quadrilaterals may degenerate by having two or more of their vertices collide, but this can be dealt with by shrinking each of the ${Q_k}$ by a tiny amount (much less than ${\varepsilon}$ and taking limits later in the argument; we leave the details to the interested reader.) If we let ${s_{k,j}}$ denote the distance between the ${a}$ -sides of ${\phi(Q_{k,j})}$ , then by uniform continuity of ${\phi}$ and the triangle inequality we have

$\displaystyle \sum_j s_{k,j} \geq (1+o(1)) M'$

as ${\varepsilon \rightarrow 0}$ . By Rengel’s inequality, we have

$\displaystyle \mathrm{mod}( \phi(Q_{k,j}) ) \geq \frac{s_{k,j}^2}{\mathrm{Area}(\phi(Q_{k,j}))};$

since ${\mathrm{mod}( \phi(Q_{k,j}) ) \leq K \mathrm{mod}( Q_{k,j} )}$ , we conclude using superadditivity that

$\displaystyle \mathrm{mod}(Q_j) \geq \frac{1}{K} \sum_k \frac{s_{k,j}^2}{\mathrm{Area}(\phi(Q_{k,j}))}$

and hence by Cauchy-Schwarz

$\displaystyle \mathrm{mod}(Q_j) \geq \frac{1}{K} \frac{(\sum_k s_{k,j})^2}{\sum_k \mathrm{Area}(\phi(Q_{k,j}))}$

and thus

$\displaystyle \frac{1}{\mathrm{mod}(Q_j)} \leq (1+o(1)) K \frac{\mathrm{Area}(\phi(Q_j))}{(M')^2}.$

Summing in ${j}$ , we obtain

$\displaystyle \frac{1}{M} \leq (1+o(1)) K \frac{M'}{(M')^2}$

giving the desired bound ${M' \leq K M}$ after sending ${\varepsilon \rightarrow 0}$ . $\Box$
It will be convenient to study analogues of the modulus when quadrilaterals are replaced by generalisations of annuli. We define a ring domain to be a region bounded between two Jordan curves ${C_1, C_2}$ , where ${C_1}$ (the inner boundary) is contained inside the interior of ${C_2}$ (the outer boundary). For instance, the annulus ${\{ z: r < |z-z_0| < R \}}$ is a ring domain for any ${z_0 \in {\bf C}}$ and ${0 < r < R < \infty}$ . In the spirit of Proposition 23, define the modulus ${\mathrm{mod}(A)}$ of a ring domain ${A}$ to be the supremum of all the quantities ${M}$ with the following property: for any Borel measurable ${\rho: A \rightarrow [0,+\infty)}$ one can find a rectifable curve ${\gamma}$ in ${A}$ winding once around the inner boundary ${C_1}$ , such that

$\displaystyle \left(\int_\gamma \rho(z)\ |dz|\right)^2 \leq \frac{2\pi}{M} \int_A \rho^2(z)\ dx dy.$

We record some basic properties of this modulus:

Exercise 35 Show that every ring domain is conformal to an annulus. (There are several ways to proceed here. One is to start by using Perron’s method to construct a harmonic function that is ${1}$ on one of the boundaries of the annulus and ${0}$ on the other. Another is to apply a logarithm map to transform the annulus to a simply connected domain with a “parabolic” group of discrete translation symmetries, use the Riemann mapping theorem to map this to a disc, and use the uniqueness aspect of the Riemann mapping theorem to figure out what happens to the symmetry.)

Exercise 36

(i) Show that the modulus of an annulus ${\{ z: r < |z-z_0| < R \}}$ is given by ${\log \frac{R}{r}}$ .

(ii) Show that if ${\phi: U \rightarrow V}$ is ${K}$ -quasiconformal and ${A}$ is an ring domain in ${U}$ , then ${\mathrm{mod}(\phi(A)) \leq K \mathrm{mod}(A)}$ . In particular, the modulus is a conformal invariant. (There is also a converse to this statement that allows for a definition of ${K}$ -quasiconformality in terms of the modulus of ring domains; see e.g. Theorem 7.2 of Lehto-Virtanen.) Use this to extend the definition of modulus of a ring domain to other domains conformal to an annulus, but whose boundaries need not be Jordan curves.

(iii) Show that if one ring domain ${A_1}$ is contained inside another ${A_2}$ (with the inner boundary of ${A_2}$ in the interior of the inner boundary of ${A_1}$ ), then ${\mathrm{mod}(A_1) \leq \mathrm{mod}(A_2)}$ .

As a basic application of this concept we have the fact that the complex plane cannot be quasiconformal to any proper subset:

Proposition 37 Let ${\phi: {\bf C} \rightarrow V}$ be a ${K}$ -quasiconformal map for some ${K \geq 1}$ ; then ${V = {\bf C}}$ .

Proof: As ${V}$ is homeomorphic to ${{\bf C}}$ , it is simply connected. Thus, if we assume for contradiction that ${V \neq {\bf C}}$ , then by the Riemann mapping theorem ${V}$ is conformal to ${D(0,1)}$ , so we may assume without loss of generality that ${V = D(0,1)}$ .

By Exercise 36(i), the moduli ${\log R}$ of the annuli ${\{ z: 1 \leq |z| \leq R \}}$ goes to infinity as ${R \rightarrow \infty}$ , and hence (by Exercise 36(ii) (applied to ${\phi^{-1}}$ ) the moduli of the ring domains ${\{ \phi(z): 1 \leq |z| \leq R \}}$ must also go to infinity. However, as the inner boundary of this domain is fixed and the outer one is bounded, all these ring domains can be contained inside a common annulus, contradicting Exercise 36(iii). $\Box$

For some further applications of the modulus of ring domains, we need the following result of Grötzsch:

Theorem 38 (Grötzsch modulus theorem) Let ${0 < r < 1}$ , and let ${A}$ be the ring domain formed from ${D(0,1)}$ by deleting the line segment from ${0}$ to ${r}$ . [Technically, ${A}$ is not quite a ring domain as defined above, but as mentioned in Exercise 36(ii), the definition of modulus remains valid in this case, as it is easy to conformally change ${A}$ to a ring domain, for instance by applying a Möbius transform to map ${A}$ to the slit plane ${{\bf C} \backslash (-\infty,0]}$ with a disk deleted and then taking a square root followed by another Möbius transformation.] Let ${A'}$ be another ring domain contained in ${D(0,1)}$ whose inner boundary encloses both ${0}$ and ${r}$ . Then ${\mathrm{mod}(A') \leq \mathrm{mod}(A)}$ .

Proof: Let ${R := \exp(\mathrm{mod}(A))}$ , then by Exercise 35 we can find a conformal map ${f}$ from ${A}$ to the annulus ${\{ z: 1 \leq |z| \leq R \}}$ . As ${A}$ is symmetric around the real axis, and the only conformal automorphisms of the annulus that preserve the inner and outer boundaries are rotations (as can be seen for instance by using the Schwarz reflection principle repeatedly to extend such automorphisms to an entire function of linear growth), we may assume that ${f}$ obeys the symmetry ${f(\overline{z}) = \overline{f(z)}}$ . Let ${\rho: A \rightarrow {\bf R}^+}$ be the function ${\rho := |f'/f|}$ , then ${\rho}$ is symmetric around the real axis. One can view ${\rho}$ as a measurable function on ${A'}$ ; from the change of variables formula we have

$\displaystyle \int_{A'} \rho^2\ dx dy \leq \int_{1 \leq |z| \leq R} \frac{1}{|z|^2}\ dx dy = 2\pi \log R,$

so in particular ${\rho}$ is square-integrable. Our task is to show that ${\mathrm{mod}(A') \leq \log R}$ ; by the definition of modulus, it suffices to show that

$\displaystyle (\int_\gamma \rho\ |dz|)^2 \geq \frac{2\pi}{\log R} \int_{A'} \rho^2\ dx dy$

for any rectifiable curve ${\gamma}$ that goes once around ${A'}$ , and thus once around ${0}$ and ${r}$ in ${D(0,1)}$ . By a limiting argument we may assume that ${\gamma}$ is polygonal. By repeatedly reflecting around the real axis whenever ${\gamma}$ crosses the line segment between ${0}$ and ${r}$ , we may assume that ${\gamma}$ does not actually cross this segment, and then by perturbation we may assume it is contained in ${A}$ . (Note that because ${\gamma}$ winds around ${0}$ and ${r}$ the same number of times, the number of times ${\gamma}$ crosses ${[0,r]}$ from below matches the number of times it crosses from above, thanks to the Alexander numbering rule.) But then by change of variables we have

$\displaystyle \int_\gamma \rho\ |dz| = \int_{f(\gamma)} \frac{d|z|}{|z|} \geq |\int_{f(\gamma)} \frac{dz}{z}| = 2\pi$

by the Cauchy integral formula, and the claim follows. $\Box$

Exercise 39 Let ${\phi_n: U \rightarrow V_n}$ be a sequence of ${K}$ -quasiconformal maps for some ${K \geq 1}$ , such that all the ${V_n}$ are uniformly bounded. Show that the ${\phi_n}$ are a normal family, that is to say every sequence in ${\phi_n}$ contains a subsequence that converges locally uniformly. (Hint: use an argument similar to that in the proof of Proposition 37, combined with Theorem 38, to establish some equicontinuity of the ${\phi_n}$ .)

There are many further basic properties of the conformal modulus for both quadrilaterals and annuli; we refer the interested reader to Lehto-Virtanen for details.

— 3. Rigidity of the hexagonal circle packing —

We return now to circle packings. In order to understand finite circle packings, it is convenient (in order to use some limiting arguments) to consider some infinite circle packings. A basic example of an infinite circle packing is the regular hexagonal circle packing

$\displaystyle {\mathcal H} := ( z_0 + S^1 )_{z_0 \in \Gamma}$

where ${\Gamma}$ is the hexagonal lattice

$\displaystyle \Gamma := \{ 2 n + 2 e^{2\pi i/3} m: n,m \in {\bf Z} \}$

and ${z_0 + S^1 := \{ z_0 + e^{i \theta}: \theta \in {\bf R} \}}$ is the unit circle centred at ${z_0}$ . This is clearly an (infinite) circle packing, with two circles ${z_0+S^1, z_1+S^1}$ in this packing (externally) tangent if and only if they differ by twice a sixth root of unity. Between any three mutually tangent circles in this packing is an open region that we will call an interstice. It is inscribed in a dual circle that meets the three original circles orthogonally and can be computed to have radius ${1/\sqrt{3}}$ ; the interstice can then be viewed as a hyperbolic triangle in this dual circle in which all three sides have infinite length.
Next we need two simple geometric lemmas, due to Rodin and Sullivan.

Lemma 40 (Ring lemma) Let ${C}$ be a circle that is externally tangent to a chain ${C_1,\dots,C_n}$ of circles with disjoint interiors, with each ${C_i}$ externally tangent to ${C_{i+1}}$ (with the convention ${C_{n+1}=C_1}$ ). Then there is a constant ${c_n}$ depending only on ${n}$ , such that the radii of each of the ${C_i}$ is at least ${c_n}$ times the radius of ${C}$ .

Proof: Without loss of generality we may assume that ${C}$ has radius ${1}$ and that the radius ${r_1}$ of ${C_1}$ is maximal among the radii ${r_i}$ of the ${C_i}$ . As the polygon connecting the centers of the ${C_i}$ has to contain ${C}$ , we see that ${r_1 \gg_n 1}$ . This forces ${r_2 \gg_n 1}$ , for if ${r_2}$ was too small then ${C_2}$ would be so deep in the cuspidal region between ${C}$ and ${C_1}$ that it would not be possible for ${C_3, C_4,\dots C_n}$ to escape this cusp and go around ${C_1}$ . A similar argument then gives ${r_3 \gg_n 1}$ , and so forth, giving the claim. $\Box$

Lemma 41 (Length-area lemma) Let ${n \geq 1}$ , and let ${{\mathcal H}_n}$ consist of those circles in ${{\mathcal H}}$ that can be connected to the circle ${0 + S^1}$ by a path of length at most ${n}$ (going through consecutively tangent circles in ${{\mathcal H}}$ ). Let ${{\mathcal C}_n}$ be circle packing with the same nerve as ${{\mathcal H}_n}$ that is contained in a disk of radius ${R}$ . Then the circle ${C_0}$ in ${{\mathcal C}_n}$ associated to the circle ${0+S^1}$ in ${{\mathcal H}_n}$ has radius ${O(\frac{R}{\log^{1/2} n})}$ .

The point of this bound is that when ${R}$ is bounded and ${n \rightarrow \infty}$ , the radius of ${C_0}$ is forced to go to zero.

Proof: We can surround ${0+S^1}$ by ${n}$ disjoint chains ${(C_{j,i})_{i=1}^{6j}, j=1,\dots,n}$ of consecutively tangent circles ${z_{j,i}+S^1}$ , ${i=1,\dots, 6j}$ in ${{\mathcal H}_n}$ . Each circle is associated to a corresponding circle in ${{\mathcal C}}$ of some radius ${r_{j,i}}$ . The total area ${\sum_{j=1}^n \sum_{i=1}^{6j} \pi r_{ij}^2}$ of these circles is at most the area ${\pi R^2}$ of the disk of radius ${R}$ . Since ${\sum_{j=1}^n \frac{1}{n} \gg \log n}$ , this implies from the pigeonhole principle that there exists ${j}$ for which

$\displaystyle \sum_{i=1}^{6j} \pi r_{ij}^2 \ll \frac{R^2}{j \log n}$

and hence by Cauchy-Schwarz

$\displaystyle \sum_{i=1}^{6j} r_{ij} \ll \frac{R}{\log^{1/2} n}.$

Connecting the centers of these circles, we obtain a polygonal path of length ${O( \frac{R}{\log^{1/2} n})}$ that goes around ${C_0}$ , and the claim follows. $\Box$
For every circle ${z_0 + S^1}$ in the circle packing ${{\mathcal H}}$ , we can form the inversion map ${\iota_{z_0}: {\bf C} \cup \{\infty\} \rightarrow {\bf C} \cup \{\infty\}}$ across this circle on the Riemann sphere, defined by setting

$\displaystyle \iota_{z_0}( z_0 + re^{i\theta} ) := z_0 + \frac{1}{r} e^{i\theta}$

for ${0 < r < \infty}$ and ${\theta \in {\bf R}}$ , with the convention that ${\iota_{z_0}}$ maps ${z_0}$ to ${\infty}$ and vice versa. These are conjugates of Möbius transformations; they preserve the circle ${z_0+S^1}$ and swap the interior with the exterior. Let ${G}$ be the group of transformations of ${{\bf C} \cup \{\infty\}}$ generated by these inversions ${\iota_{z_0}}$ ; this is essentially a Schottky group (except for the fact that we are are allowing for conjugate Möbius transformations in addition to ordinary Möbius transformations). Let ${I}$ denote the union of all the interstices in ${{\mathcal H}}$ , and let ${GI := \bigcup_{g \in G} g(I)}$ be the union of the images of the interstitial regions ${I}$ under all of these transformations. We have the following basic fact:

Proposition 42 ${{\bf C} \backslash GI}$ has Lebesgue measure zero.

Proof: (Sketch) I thank Mario Bonk for this argument. Let ${G {\mathcal H}}$ denote all the circles formed by applying an element of ${G}$ to the circles in ${{\mathcal H}}$ . If ${z}$ lies in ${{\bf C} \backslash GI}$ , then it lies inside one of the circles in ${{\mathcal H}}$ , and then after inverting through that circle it lies in another circle in ${{\mathcal H}}$ , and so forth; undoing the inversions, we conclude that ${z}$ lies in infinite number of nested circles. Let ${C}$ be one of these circles. ${GI}$ contains a union of six interstices bounded by ${C}$ and a cycle of six circles internally tangent to ${C}$ and consecutively externally tangent to each other. Applying the same argument used to establish the ring lemma (Lemma 40), we see that the six internal circles have radii comparable to that of ${C}$ , and hence ${GI}$ has density ${\gg 1}$ in the disk enclosed by ${C}$ , which also contains ${z}$ . The ring lemma also shows that the radius of each circle in the nested sequence is at most ${1-c}$ times the one enclosing it for some absolute constant ${c>0}$ , so in particular the disks shrink to zero in size. Thus ${z}$ cannot be a point of density of ${{\bf C} \backslash GI}$ , and hence by the Lebesgue density theorem this set has measure zero. $\Box$

We also need another simple geometric observation:

Exercise 43 Let ${C_1,C_2,C_3}$ be mutually externally tangent circles, and let ${C'_1, C'_2, C'_3}$ be another triple of mutually external circles, with the same orientation (e.g. ${C_1,C_2,C_3}$ and ${C'_1,C'_2,C'_3}$ both go counterclockwise around their interstitial region). Show that there exists a Möbius transformation ${\phi}$ that maps each ${C_i}$ to ${C'_i}$ and which maps the interstice of ${C_1,C_2,C_3}$ conformally onto the interstice of ${C'_1,C'_2, C'_3}$ .

Now we can give a rigidity result for the hexagonal circle packing, somewhat in the spirit of Theorem 4 (though it does not immediately follow from that theorem), and also due to Rodin and Sullivan:

Proposition 44 (Rigidity of infinite hexagonal packing) Let ${{\mathcal C}}$ be an infinite circle packing in ${{\bf C}}$ with the same nerve as the hexagonal circle packing ${{\mathcal H}}$ . Then ${{\mathcal C}}$ is in fact equal to the hexagonal circle packing up to affine transformations and reflections.

Proof: By applying a reflection we may assume that ${{\mathcal C}}$ and ${{\mathcal H}}$ have the same orientation. For each interstitial region ${I_j}$ of ${{\mathcal H}}$ there is an associated interstitial region ${I'_j}$ of ${{\mathcal C}}$ , and by Exercise 43 there is a Möbius transformation ${T_j: I_j \rightarrow I'_j}$ . These can be glued together to form a map ${\phi_0}$ that is initially defined (and conformal) on the interstitial regions ${I =\bigcup_j I_j}$ ; we would like to extend it to the entire complex plane by defining it also inside the circles ${z_j + S^1}$ .

Now consider a circle ${z_j+S^1}$ in ${{\mathcal H}}$ . It is bounded by six interstitial regions ${I_1,\dots,I_6}$ , which map to six interstitial regions ${I'_1,\dots,I'_6}$ that lie between the circle ${C_0}$ corresponding to ${z_j+S^1}$ and six tangent circles ${C_1,\dots,C_6}$ . By the ring lemma, all of the circles ${C_1,\dots,C_6}$ have radii comparable to the radius ${r_j}$ of ${C_0}$ . As a consequence, the map ${\phi_0}$ , which is defined (and piecewise Möbius) on the boundary of ${z_j + S^1}$ as a map to the boundary of ${C_0}$ , has derivative comparable in magnitude to ${r_j}$ also. By extending this map radially (in the sense of defining ${\phi(z_j + r e^{i\theta}) := w_j + r r_j (\phi(z_j + e^{i\theta})-w_j)}$ for ${0 < r < 1}$ and ${\theta \in {\bf R}}$ , where ${w_j}$ is the centre of ${C_0}$ , we see from Theorem 29 that we can extend ${\phi_0}$ to be ${K}$ -quasiconformal in the interior of ${z_j+S^1}$ except possibly at ${z_j}$ for some ${K=O(1)}$ , and to a homeomorphism from ${{\bf C}}$ to the region ${\phi_0({\bf C})}$ consisting of the union of the disks in ${{\mathcal C}}$ and their interstitial regions. By many applications of Theorem 34, ${\phi_0}$ is now ${K}$ -quasiconformal on all of ${{\bf C}}$ , and conformal in the interstitial regions ${I}$ . By Proposition 37, ${\phi_0}$ surjects onto ${{\bf C}}$ , thus the circle packing ${{\mathcal C}}$ and all of its interstitial regions cover the entire complex plane.

Next, we use a version of the Schwarz reflection principle to replace ${\phi_0}$ by another ${K}$ -quasiconformal map that is conformal on a larger region than ${I}$ . Namely, pick a circle ${z_j+S^1}$ in ${{\mathcal H}}$ , and let ${C_0}$ be the corresponding circle in ${{\mathcal C}}$ . Let ${\iota_j}$ and ${\iota'_j}$ be the inversions across ${z_j+S^1}$ and ${C_0}$ respectively. Note that ${\phi_0}$ maps the circle ${z_j+S^1}$ to ${C_0}$ , with the interior mapping to the interior and exterior mapping to the exterior. We can then define a modified map ${\phi_1}$ by setting ${\phi_1(z)}$ equal to ${\phi_0(z)}$ on or outside ${z_j+S_1}$ , and ${\phi_1(z)}$ equal to ${\iota'_j \circ \phi_0 \circ \iota_j(z)}$ inside ${z_j+S_1}$ (with the convention that ${\phi_0}$ maps ${\infty}$ to ${\infty}$ ). This is still an orientation-preserving function ${{\bf C}}$ ; by Theorem 34 it is still ${K}$ -quasiconformal. It remains conformal on the interstitial region ${I}$ , but is now also conformal on the additional interstitial region ${\iota_j(I)}$ . Repeating this construction one can find a sequence ${\phi_n:{\bf C} \rightarrow {\bf C}}$ of ${K}$ -quasiconformal maps that map each circle ${z_j+S^1}$ to their counterparts ${C_0}$ , and which are conformal on a sequence ${I_n}$ of sets that increase up to ${GI}$ . By Exercise 39, the restriction of ${\phi_n}$ to any compact set forms a normal family (the fact that the circles ${z_j+S^1}$ map to the circles ${C_0}$ will give the required uniform boundedness for topological reasons), and hence (by the usual diagonalisation argument) the ${\phi_n}$ themselves are a normal family; similarly for ${\phi_n^{-1}}$ . Thus, by passing to a subsequence, we may assume that the ${\phi_n}$ converge locally uniformly to a limit ${\phi}$ , and that ${\phi_n^{-1}}$ also converge locally uniformly to a limit which must then invert ${\phi}$ . Thus ${\phi}$ is a homeomorphism, and thus ${K}$ -quasiconformal by Theorem 33. It is conformal on ${GI}$ , and hence by Proposition 32 it is conformal. But the only conformal maps of the complex plane are the affine maps (see Proposition 15 of this previous blog post), and hence ${{\mathcal C}}$ is an affine copy of ${{\mathcal H}}$ as required. $\Box$

By a standard limiting argument, the perfect rigidity of the infinite circle packing can be used to give approximate rigidity of finite circle packings:

Corollary 45 (Approximate rigidity of finite hexagonal packings) Let ${\varepsilon>0}$ , and suppose that ${n}$ is sufficiently large depending on ${\varepsilon}$ . Let ${{\mathcal H}_n}$ and ${{\mathcal C}_n}$ be as in Lemma 41. Let ${r_0}$ be the radius of the circle ${C_1}$ in ${{\mathcal C}_n}$ associated to ${0+S_1}$ , and let ${r_1}$ be the radius of an adjacent circle ${C_1}$ . Then ${1-\varepsilon \leq \frac{r_1}{r_0} \leq 1+\varepsilon}$ .

Proof: We may normalise ${r_0=1}$ and ${C_0=S^1}$ . Suppose for contradiction that the claim failed, then one can find a sequence ${n}$ tending to infinity, and circle packings ${{\mathcal C}_n}$ with nerve ${{\mathcal H}_n}$ with ${C_0 = C_{0,n} = S^1}$ , such that the radius ${r_{1,n}}$ of the adjacent circle ${C_1 = C_{1,n}}$ stays bounded away from ${1}$ . By many applications of the ring lemma, for each circle ${z + S^1}$ of ${{\mathcal H}}$ , the corresponding circle ${C_{z,n}}$ in ${{\mathcal C}_n}$ has radius bounded above and below by zero. Passing to a subsequence using Bolzano-Weierstrass and using the Arzela-Ascoli diagonalisation argument, we may assume that the radii ${r_{z,n}}$ of these circles converge to a positive finite limit ${r_{z,\infty}}$ . Applying a rotation we may also assume that the circles ${C_{1,n}}$ converge to a limit circle ${C_{1,\infty}}$ (using the obvious topology on the space of circles); we can also assume that the orientation of the ${{\mathcal C}_n}$ does not depend on ${n}$ . A simple induction then shows that ${C_{z,n}}$ converges to a limit circle ${C_{z,\infty}}$ , giving a circle packing ${{\mathcal C}_\infty}$ with the same nerve as ${{\mathcal H}}$ . But then by Lemma 44, ${{\mathcal C}_\infty}$ is an affine copy of ${{\mathcal H}}$ , which among other things implies that ${r_{1,\infty} = r_{0,\infty} = 1}$ . Thus ${r_{1,n}}$ converges to ${1}$ , giving the required contradiction. $\Box$

A more quantitative version of this corollary was worked out by He. There is also a purely topological proof of the rigidity of the infinite hexagonal circle packing due to Schramm.

— 4. Approximating a conformal map by circle packing —

Let ${U}$ be a simply connected bounded region in ${{\bf C}}$ with two distinct distinguished points ${z_0, z_1 \in U}$ . By the Riemann mapping theorem, there is a unique conformal map ${\phi: U \rightarrow D(0,1)}$ that maps ${z_0}$ to ${0}$ and ${z_1}$ to a positive real. However, many proofs of this theorem are rather nonconstructive, and do not come with an effective algorithm to locate, or at least approximate, this map ${\phi}$ .

It was conjectured by Thurston, and later proven by Rodin and Sullivan, that one could achieve this by applying the circle packing theorem (Theorem 3) to a circle packing in ${U}$ by small circles. To formalise this, we need some more notation. Let ${\varepsilon>0}$ be a small number, and let ${\varepsilon \cdot {\mathcal H}}$ be the infinite hexagonal packing scaled by ${\varepsilon}$ . For every circle in ${\varepsilon \cdot {\mathcal H}}$ , define the flower to be the union of this circle, its interior, the six interstices bounding it, and the six circles tangent to the circle (together with their interiors). Let ${C_0}$ be a circle in ${\varepsilon \cdot {\mathcal H}}$ such that ${z_0}$ lies in its flower. For ${\varepsilon}$ small enough, this flower is contained in ${U}$ . Let ${{\mathcal I}_\varepsilon}$ denote all circles in ${\varepsilon \cdot {\mathcal H}}$ that can be reached from ${C_0}$ by a finite chain of consecutively tangent circles in ${\varepsilon \cdot {\mathcal H}}$ , whose flowers all lie in ${U}$ . Elements of ${{\mathcal I}_\varepsilon}$ will be called inner circles, and circles in ${\varepsilon \cdot {\mathcal H}}$ that are not an inner circle but are tangent to it will be called border circles. Because ${U}$ is simply connected, the union of all the flowers of inner circles is also simply connected. As a consequence, one can traverse the border circles by a cycle of consecutively tangent circles, with the inner circles enclosed by this cycle. Let ${{\mathcal C}_\varepsilon}$ be the circle packing consisting of the inner circles and border circles. Applying Theorem 3 followed by a Möbius transformation, one can then find a circle packing ${{\mathcal C}'_\varepsilon}$ in ${D(0,1)}$ with the same nerve and orientation as ${{\mathcal C}_\varepsilon}$ , such that all the circles in ${{\mathcal C}'_\varepsilon}$ associated to border circles of ${{\mathcal C}_\varepsilon}$ are internally tangent to ${D(0,1)}$ . Applying a Möbius transformation, we may assume that the flower containing ${z_0}$ in ${{\mathcal C}_\varepsilon}$ is mapped to the flower containing ${0}$ , and the flower containing ${z_1}$ is mapped to a flower containing a positive real. (From the exercise below ${z_1}$ will lie in such a flower for ${\varepsilon}$ small enough.)

Let ${U_\varepsilon}$ be the union of all the solid closed equilateral triangles formed by the centres of mutually tangent circles in ${{\mathcal C}_\varepsilon}$ , and let ${D_\varepsilon}$ be the corresponding union of the solid closed triangles from ${{\mathcal C}'_\varepsilon}$ . Let ${\phi_\varepsilon}$ be the piecewise affine map from ${U_\varepsilon}$ to ${D_\varepsilon}$ that maps each triangle in ${U_\varepsilon}$ to the associated triangle in ${D_\varepsilon}$ .

Exercise 46 Show that ${U_\varepsilon}$ converges to ${U}$ as ${\varepsilon \rightarrow 0}$ in the sense that for every compact ${K \subset U}$ , we have ${K \subset U_\varepsilon}$ for all sufficiently small ${\varepsilon}$ . In particular, ${z_1}$ lies in ${U_\varepsilon}$ for sufficiently small ${\varepsilon}$ .

Exercise 47 By modifying the proof of the length-area lemma, show that all the circles ${C}$ in ${{\mathcal C}'_\varepsilon}$ have radius that goes uniformly to zero as ${\varepsilon \rightarrow 0}$ . (Hint: for circles ${C}$ deep in the interior, the length-area lemma works as is; for circles ${C}$ near the boundary, one has to encircle ${C}$ by a sequence of chains that need not be closed, but may instead terminate on the boundary of ${D(0,1)}$ . The argument may be viewed as a discrete version of the one used to prove Theorem 20.) Using this and the previous exercise, show that ${D_\varepsilon}$ converges to ${D(0,1)}$ in the sense that for every compact ${K \subset D(0,1)}$ , we have ${K \subset D_\varepsilon}$ for all sufficiently small ${\varepsilon}$ .

From Corollary 45 we see that as ${\varepsilon \rightarrow 0}$ , the circles in ${{\mathcal C}'_\varepsilon}$ corresponding to adjacent circles of ${{\mathcal C}_\varepsilon}$ in a fixed compact subset ${R}$ of ${U}$ have radii differing by a ratio of ${1+o(1)}$ . We conclude that in any compact subset ${R'}$ of ${D(0,1)}$ , adjacent circles in ${{\mathcal C}'_\varepsilon}$ in ${R'}$ also have radii differing by a ratio of ${1+o(1)}$ , which implies by trigonometry that the triangles of ${D_\varepsilon}$ in ${R'}$ are approximately equilateral in the sense that their angles are ${\frac{\pi}{3}+o(1)}$ . By Theorem 29 ${\phi_\varepsilon}$ is ${1+o(1)}$ -quasiconformal on each such triangle, and hence by Theorem 34 it is ${1+o(1)}$ -quasiconformal on ${R}$ . By Exercise 39 every sequence of ${\phi_\varepsilon}$ has a subsequence which converges locally uniformly on ${U}$ , and whose inverses converge locally uniformly on ${D}$ ; the limit is then a homeomorphism from ${U}$ to ${D}$ that maps ${z_0}$ to ${0}$ and ${z_1}$ to a positive real. By Theorem 33 the limit is locally ${1}$ -quasiconformal and hence conformal, hence by uniqueness of the Riemann mapping it must equal ${\phi}$ . As ${\phi}$ is the unique limit point of all subsequences of the ${\phi_\varepsilon}$ , this implies (by the Urysohn subsequence principle) that ${\phi_\varepsilon}$ converges locally uniformly to ${\phi}$ , thus making precise the sense in which the circle packings converge to the Riemann map.

32 comments

Comments feed for this article

12 April, 2018 at 11:44 am

Tom Hutchcroft

Thanks for the great post, Terry. I would like to use this comment to direct your readers towards some further reading about the beautiful theory of circle packing and its applications, and in particular to its applications in probability with which I am most familiar.

Good places for more background are Ken Stephenson’s book, and Steffen Rhode’s survey of Oded Schramm’s contributions to the subject https://arxiv.org/pdf/1007.2007.pdf.

First, regarding the material covered in the post:

There is an entirely combinatorial proof of the existence part of the Circle Packing Theorem due to Brightwell and Scheinerman https://epubs.siam.org/doi/abs/10.1137/0406017.

A very short proof of uniqueness for finite circle packings was found by Schramm, who (as I understand it) anonymously added it to this wikipedia article https://en.wikipedia.org/wiki/Circle_packing_theorem. It does not appear elsewhere as far as I know.

The question of existence and uniqueness of circle packings of infinite triangulations in prescribed domains was studied by He and Schramm
https://link.springer.com/article/10.1007/BF02570699 https://www.jstor.org/stable/2946541, who in particular proved the natural analogue of the uniformization theorem in this context, namely that every triangulation of the plane can be circle packed in either the Euclidean plane or the hyperbolic plane, but not both. The earlier paper of Schramm that you mentioned (http://www.ams.org/journals/jams/1991-04-01/S0894-0347-1991-1076089-9/home.html) implies that these packings are unique up to reflections and Mobius transformations. They also proved that, if the triangulation has bounded degrees, then it gets packed in the Euclidean plane if and only if simple random walk on it is recurrent (i.e., visits every vertex infinitely often almost surely). They also studied circle packings of non-simply connected domains, a topic which is closely related to the Koebe conjecture.

The existence and uniqueness problems for infinite packings were later revisited by He in the wonderful paper https://arxiv.org/abs/math/9901148, which in my opinion has the best proofs of both results. His proofs also apply to more general “disk patterns” in which circles are required to intersect with specified angles rather than necessarily being tangent.

Now, for applications in probability:

As I mentioned already, He and Schramm proved that a bounded degree triangulation of the plane can be circle packed in the hyperbolic plane if and only it is transient for simple random walk. This result was extended by Gurel-Gurevich, Nachmias, and Suoto (https://projecteuclid.org/euclid.ecp/1483671681), who proved that the random walk on a bounded degree triangulation circle packed in a domain D is transient if and only if Brownian motion on D is transient, i.e. leaves D in finite time almost surely.

Benjamini and Schramm (https://link.springer.com/article/10.1007/s002220050109) proved that in this case, the simple random walk on the circle packed triangulation converges to a point in the ideal boundary of the hyperbolic plane, and that the law of the limit point is non-atomic and has full support. They used this result to deduce that a bounded degree planar graph admits non-constant bounded harmonic functions if and only if it is transient (equivalently, the invariant sigma-algebra of the random walk on the triangulation is non-trivial if and only if the walk is transient), and in this case it also admits non-constant bounded harmonic functions of finite Dirichlet energy. They also proved the same result using square tiling instead of circle packing in https://projecteuclid.org/euclid.aop/1065725179. I should mention here that the regularity of the harmonic measures on the boundary is not very well understood. For example, it is an open problem to determine whether the harmonic measure of the random walk on the 7-regular hyperbolic triangulation is absolutely continuous with respect to Lebesgue (it is believed not to be, and should have a fractal structure).

The result of Benjamini and Schramm just mentioned allows one to construct harmonic functions on the graph by taking functions on the boundary and integrating them against the harmonic measure. Angel, Barlow, Gurel-Gurevich, and Nachmias (https://projecteuclid.org/euclid.aop/1463410036) proved that, in fact, every bounded harmonic function on a bounded degree triangulation arises in this way. In other words, the boundary of the hyperbolic plane can be identified with the Poisson boundary of the triangulation. They also proved the stronger result that every positive harmonic function on the triangulation admits a representation the harmonic extension of a measure on the boundary of the hyperbolic plane, i.e. that the boundary of the hyperbolic plane can be identified with the Martin boundary of the triangulation. In my paper https://arxiv.org/pdf/1707.07751.pdf, I prove a related representation theorem for harmonic Dirichlet functions on bounded degree triangulations. Angel, Barlow, Gurel-Gurevich and Nachmias also proved various quite strong estimates for the random walk on the triangulation, to the effect that the random walk on the circle packing behaves similarly to a quasi-conformal image of Brownian motion. Their results regarding the Poisson boundary followed earlier work by Georgakopoulos (https://arxiv.org/abs/1301.1506), which established a corresponding result for square tilings. Both results were revisited in my work with Peres (https://projecteuclid.org/euclid.ejp/1511578855), which gave a simplified and unified proof that works for both embeddings.

Circle packing has been very important in the study of random planar maps. In particular, Benjamini and Schramm (https://projecteuclid.org/euclid.ejp/1461097653) used circle packing to prove that every “distributional limit” of finite, bounded degree planar graphs is almost surely recurrent. (These limits are now commonly known as Benjamini-Schramm limits.) Alternative proofs of their result have recently been given by Angel, Nachmias, Ray, and myself (https://arxiv.org/abs/1501.04677) and by Lee (https://arxiv.org/abs/1701.01598).

Gurel-Gurevich and Nachmias (https://arxiv.org/abs/1206.0707) later improved upon the methods of Benjamini and Schramm to prove that the Uniform Infinite Planar Triangulation (UIPT) is recurrent. The UIPT is defined to be the distributional limit of uniform triangulations of the sphere with n vertices as n goes to infinity. The circle packing of the UIPT is conjectured to converge under rescaling to so-called Liouville Quantum Gravity (LQG). Despite the recent and great advances in the understanding of LQG (which includes too many papers and authors to list here), this particular conjecture still seems quite far off.

Some more papers using circle packing to study probabilistic questions on planar graphs include https://projecteuclid.org/euclid.ecp/1456943503, https://arxiv.org/abs/1603.07320, https://www.math.ubc.ca/~mathav/index_files/qs.pdf.

15 April, 2018 at 8:00 am

j.c.

Thanks very much for this helpful overview! Your paper with Peres on boundaries of planar graphs for both square tilings and circle packings is particularly interesting.

One non-mathematical comment: Schramm was not anonymous on wikipedia (his username was “OdedSchramm” https://en.wikipedia.org/wiki/User:OdedSchramm ) and his contributions were quite extensive. For instance, the history of the wikipedia page on the circle packing theorem shows that he created the page and wrote the majority of it from 28 – 31 March 2008; for instance, his elementary proof of uniqueness was added in this edit https://en.wikipedia.org/w/index.php?title=Circle_packing_theorem&diff=202165964&oldid=202158966

14 April, 2018 at 2:10 pm

Asaf Nachmias

Here’s a neat elementary argument due to Ohad Feldheim and Ori Gurel-Gurevich that avoids the topology in the proof of Prop 17. It’s stated in the Euclidean rather than the hyperbolic setting, but it seems to imply Prop 17 cause one can calculate the Euclidean centers and radii from the hyperbolic ones.

Assume you have an assignment of positive numbers (lengths) $\{\ell_e\}_{e\in E}$ to the edges of a maximal planar graph so that for each internal vertex $v$ the angles formed at $v$ by triangles with edge lengths corresponding to the edges of the faces incident to $v$ sum to $2\pi$ . Then there is a proper drawing of the graph where an edge $e$ is drawn as a straight line segment of length $\ell_e$ .

Proof: By induction on the number of vertices. For 3 vertices it is obvious. Otherwise take an internal vertex $v$ and draw the triangles corresponding to the faces incident $v$ . Since the sum of angles is $2\pi$ everything “fits” and you get a polygon where $v$ is somewhere inside. Triangulate the polygon (two ears theorem) and record the lengths of the diagonals you added. You now have a new maximal planar graph with one vertex less and the new assignment of lengths also give $2\pi$ angle sum at each internal vertex. Use the induction hypothesis to draw the new graph with straight lines, and now the location of $v$ and the edges emanating from it are determined since the polygon above is drawn exactly the same, so you can add them.

16 April, 2018 at 6:30 am

Terence Tao

This is a nice use of the two ears theorem! It doesn’t fit well pedagogically with the arrangement I have in my blog, but it is certainly worth noting.

15 April, 2018 at 5:04 am

John Mangual

It seems quite appealing to build a complex analysis out of arrangements of circles or squares. There are some excellent graphics on the internet (that may not have been available before). E.g. on Wikipedia https://en.wikipedia.org/wiki/Circle_packing#Uniform_packings
My best guess is that holomorphic functions arise naturally in trying to solve differential equations such as Laplace equation or heat equation $\nabla^2 \phi = 0$ . However, there is no free lunch since Riemann existence theorem requires Green’s functions to solve.

15 April, 2018 at 5:24 pm

geoishard

This is lovely! Unfortunately I’m confused by Exercise 31. If I’m not being silly, it contradicts Theorem 5.14 (and the sentence following 5.14) in this removability survey: https://arxiv.org/pdf/1503.02582.pdf. But it seems to be important, so maybe I am being silly. Any ideas/help?

15 April, 2018 at 5:34 pm

Terence Tao

Oops, I had omitted the rather important hypothesis of quasiconformality, now added.

15 April, 2018 at 6:12 pm

geoishard

Ah, thanks! Very nice.

15 April, 2018 at 9:00 pm

Lexing Ying

Thank you! In Exercise (30), should it be (K-1)/(K+1)?

[Corrected, thanks – T.]

17 April, 2018 at 7:47 pm

Dan Asimov

So now I’m wondering what the derivative of a 1-parameter family of circle-packings is …

17 April, 2018 at 11:15 pm

Coloring Problems for Arrangements of Circles (and Pseudocircles) | Combinatorics and more

[…] Koebe’s circle packing theorem (see this recent post) this is precisely the four color theorem so the answer is […]

20 April, 2018 at 4:27 am

John Mangual

Have you seen the notes of Stanislav Smirnov “Discrete Complex Analysis and Probability” https://arxiv.org/abs/1009.6077 these are from 8 years ago.

Actually these are totally different from the circle packings approach outlined by Thurston, Rodin, Sullivan, Stephenson and others. There’s also “Discrete Differential Geometry” by Bobenko-Suris. http://page.math.tu-berlin.de/~bobenko/ddg-book.html

I have trouble memorizing the Cauchy-Riemann equations, so I start with the Taylor approximation $f(z+dz) = f(z) + f'(z) dz$ and I observe it could not matter if $dz = dx, idy, \cos \theta dx + \sin \theta dy$ . I’m not 100% sure I can even do it still. Now that I’ve dropped out of school, I rarely use this material. $f(z+dx) = f(z) + (\partial_x f) dx$ however $f(z + idy) = f(z) + i(\partial y f)dy$ .

So I will obtain $\partial_x f = i \partial y f$ or $(\partial x - i \partial y ) f = \frac{\partial}{\partial \overline{z}} f = 0$ so that looks right. Good.

For the longest time, I’ve wondered… what’s so special about the Cauchy-Riemann equations? I haven’t even used this result in any intelligent way yet. For now, I content myself to know this is connected to circle packings and the ising model.

20 April, 2018 at 10:19 am

Anonymous

In Exercise 10, should the first sentence read “Let G be a maximal planar graph with at least four vertices” rather than “at most”?

[Corrected, thanks – T.]

24 April, 2018 at 3:37 pm

Anonymous

same exercise (10): should the last set be G\{v,v1,…,vd} rather than {v,v1,…,vd}?

[Corrected, thanks -T.]

30 April, 2018 at 11:28 am

Anonymous

In Exercise 15(i), should the last formula be
cos alpha_1(r_1,infty,infty) = 1 – 2exp(-2r_1)?

[Corrected, thanks – T.]

2 May, 2018 at 2:18 pm

246C notes 3: Univalent functions, the Loewner equation, and the Bieberbach conjecture | What's new

[…] To prove (i), it suffices from (11) and the Schwarz-Pick lemma (Exercise 13 from Notes 2) to establish this claim when . We can also assume that since the claim is trivial when . From the […]

6 May, 2018 at 4:00 am

John Mangual

Is are discrete conformal mappings such as (square tilings and circle packings) quasiconformal? We have that $\mathbb{Z}$ and $\mathbb{Z} \times \big(\mathbb{Z}/2\mathbb{Z}\big)$

Looks like sections 1 on Circle Packings and Section 2 on Quasiconformal maps combine in into sections 3 and 4 on rigidity and approximation.

You can draw a map of the United States out of squares using discrete conformal mappings. I wonder how they handled Utah-Arizona-New Mexico-Colorado?

These notes of Kenyon and Parry offer six models of the hyperbolic plane. At the moment I can only think of $\mathbb{H}$ and $\mathbb{D}$ .

Click to access cannon.pdf

10 May, 2018 at 2:19 pm

Anonymous

In Exercise 35, part (ii), the phi and mod should be interchanged.

[Corrected, thanks – T.]

29 May, 2018 at 9:30 am

246C notes 4: Brownian motion, conformal invariance, and SLE | What's new

[…] This gives an inequality similar in spirit to the Grötzsch modulus estimate from Notes 2: […]

16 July, 2018 at 7:25 am

Nick Lohr

In the two paragraphs following right after the statement in Theorem 11, you mention Theorem 14 without stating it. Do you mean to say Theorem 11? In the last paragraph before Exercise 12, you say, “It remains to show Theorem 7.” Do you mean Theorem 11?

Also, isn’t it true that there exists a unique hyperbolic triangle with all sides infinite in $\overline{D(0,1)}$ up to reflections and Möbius automorphisms? If so, is there a reason why its omitted from this discussion?

Lastly, a pedagogical question: Is it possible to reformulate Theorem 7 in the hyperbolic setting and prove Theorem 3,4 from it? This way one can get rid of Theorem 11 entirely and just deal with Theorem 14, right?

17 July, 2018 at 3:04 pm

Terence Tao

Thanks for the corrections. While a hyperbolic triangle with all infinite sides is indeed unique up to isometries, a hyperbolic triangle with three tangent circles centred at the vertices is not unique in this fashion, and this is really the geometric object of relevance in circle packings. Also some of the continuity statements fail if one tries to add this endpoint to the configuration space of triangles.

One can rearrange the presentation of the various theorems slightly, and one can certainly phrase Theorem 7 in the hyperbolic setting by specialising to the case when one of the circles is the exterior of the unit disk, but the inductive step still requires the use of Mobius transformations that preserve the Riemann sphere but not the hyperbolic disk, so I don’t see how to easily move the proof to entirely lie within the hyperbolic setting.

15 February, 2019 at 9:04 am

Nick Lohr

Thank you. A few small typos: Before and after you use Cauchy-Schwarz in the proof of Caratheodory’s theorem the $r$ in the integrals should be $r_n$ . In the proof of Proposition 23, the first equality should be an integral over $\gamma$ and not $\phi$ . Also, in this proof, you use $dz\overline{dz}=dxdy$ but isn’t it $dz\overline{dz}=-2idxdy$ ?

[Corrected, thanks – T.]

1 April, 2019 at 7:08 am

Nick Lohr

Some more typos. In the statement and proof of Proposition 31, the $R$ should be $T$ , the $y_j$ ‘s should be just $y$ ‘s, and there is a $x'_y$ that should be $x'_j$ . Right before Exercise 35 when you are defining modulus for the annulus, the $dz d \overline{z}$ should be just $dxdy$ to avoid complex numbers in the inequality.

[Corrected, thanks – T.]

9 April, 2019 at 9:43 am

Nick Lohr

Some more (important) typos (I’m doing this for my senior thesis which is why I am being so pesky). In the first indented line in Theorem 38, I think we only know $\leq$ in the first equality. In the second indented line in this theorem, the $d|z|$ should be $|dz|$ and the $\leq$ should be flipped to $\geq$ (with $2i$ underneath the area form). In the last indented line of the theorem, the $d|z|$ ‘s should be $|dz|$ ‘s and the $\leq$ needs to be flipped to $\geq$ .

[Corrected, thanks – T.]

31 August, 2020 at 9:22 pm

Nick Lohr

What is the definition of homotopic triangulations used here? Beardon and Stephenson define homotopic closed chains within a simplicial 2-complex via “local modifications.” Is it a similar definition to this?

Also, is there a good reference for the topological fact that any two triangulations of a maximal planar graph of atleast four vertices are homotopic up to reflection (to reverse orientation)?

7 September, 2020 at 2:21 pm

Tom Hutchcroft

For the second question: This fact follows from Lemma 8.42 in Probability on Trees and Networks by Lyons and Peres https://rdlyons.pages.iu.edu/prbtree/ They cite papers of Whitney (1932) and Imrich (1975) which I could not find copies of online.

27 February, 2021 at 9:47 am

246C notes 1: Meromorphic functions on Riemann surfaces, and the Riemann-Roch theorem | What's new

[…] set of notes: 246B Notes 4. Next set of notes: Notes 2. The fundamental object of study in real differential geometry are the real manifolds: Hausdorff […]

28 April, 2022 at 10:36 pm

Anonymous

In Exercise 15(ii), do you mean d(\gamma(s), \gamma(t))= c|s-t|, instead of d(\gamma(s)-gamma(t))?

[Corrected, thanks – T.]

9 May, 2022 at 2:48 pm

Anonymous

How does the spherical maximal operator related to circle packing? Does one help understand the other in anyway?

10 May, 2022 at 6:05 pm

Anonymous

In the proof of Theorem 29, in the sixth line of the inequality chain, dx should be inside the absolute value.

[Corrected, thanks – T.]

11 May, 2022 at 10:26 pm

Anonymous

In the proof of theorem 29, in the big chain of inequalities, I believe that the final equality should be an inequality instead.
\phi(T + iy) and \phi(iy) definitely lie on opposite sides of the rectangle, however they might not lie on the same imaginary line.

[Corrected, thanks – T.]

13 May, 2022 at 1:52 pm

Anonymous

Does “rigidity of circle packing” omit a set of measure zero, while the “rigidity of hexagonal packing” is truly rigid?

	Yingyuan Li on Analysis II
	Anonymous on Analysis II
	Anonymous on Analysis II
	Yingyuan Li on Analysis II
	Yingyuan Li on Analysis II
	Yingyuan Li on Analysis II
	Yingyuan Li on Analysis II
	Jamie on On writing
	Anonymous on On writing
	Terence Tao on PCAST Working Group on Generat…
	Yingyuan Li on Analysis II
	Sam on 245A, Notes 5: Differentiation…
	Johan Aspegren on PCAST Working Group on Generat…
	Sam on 245A, Notes 5: Differentiation…
	wbshu on 247B, Notes 1: Restriction…

246C notes 2: Circle packings, conformal maps, and quasiconformal maps

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

32 comments

Leave a Reply Cancel reply

For commenters

246C notes 2: Circle packings, conformal maps, and quasiconformal maps

Share this:

Like this:

Recent Comments

Articles by others

Diversions

Mathematics

Selected articles

Software

The sciences

Top Posts

Archives

Categories

The Polymath Blog

32 comments

Leave a Reply Cancel reply

For commenters