j. differential geometry 63 (2003) 97-129

COMBINATORIAL RICCI FLOWS ON SURFACES

BENNETT CHOW & FENG LUO

Abstract

We show that the analogue of Hamilton’s Ricci flow in the combinatorial setting produces solutions which converge exponentially fast to Thurston’s circle packing on surfaces. As a consequence, a new proof of Thurston’s existence of circle packing theorem is obtained. As another consequence, Ricci flow suggests a new algorithm to find circle packings.

1. Introduction

1.1

For a compact surface with a Riemannian metric (X, g_{ij}), R. Hamilton in [7] introduced the 2-dimensional Ricci flow defined by the equation \frac{dg_{ij}}{dt} = −2Kg_{ij} where K is the Gaussian curvature of the surface. It is proved in [7] and [3] that for any closed surface with any initial Riemannian metric, the solution of the Ricci flow exists for all time, and after normalizing the solution to have a fixed area, the solution converges to a constant curvature metric conformal to the initial metric as time goes to infinity. The purpose of the paper is to study the analogous flow in the combinatorial setting. The simplest case of our setup is as follows. Given a triangulated surface, we assign to each vertex a positive radius and realize the surface by a piecewise flat cone metric with singularities at the vertices where the length of an edge is the sum of the two radii associated to the end points. We call these the (tangential type) circle-packing metrics based on the triangulation. We consider a natural flow (the combinatorial Ricci flow) on the space of all tangential type circle-packing metrics. Our results give a complete description of the asymptotic behavior of the solution of the Ricci flow. If we use hyperbolic geometry as the background metric, then for compact surfaces of negative Euler characteristic, we show that the combinatorial Ricci flow has solutions for all time for any initial metric and converges exponentially fast to the circle packing metric constructed by Thurston.

Received 11/18/2002.

1.2

For simplicity, we shall state our results for triangulations on compact surfaces without boundary. For the most general version involving cellular-decompositions, see §2, §5 and §6.

Suppose X is a closed surface and T is a triangulation on X. Let V = {v_{1}, v_{2}, …, v_{N}} be the set of vertices in T. The set of all edges and triangles in T are denoted by E and F. Unless mentioned otherwise a weight on the triangulation is a function Φ : E → [0, π/2]. (In Lemma 2.3, Proposition 3.1 and Proposition 4.1, we allow the weight to be Φ : E → [0, π)).

Given a weighted triangulation (T, Φ) of a compact surface X, we consider the circle packing metrics on the surface X based on (T, Φ) defined as follows.

To each vertex v_{i} in the triangulation T, assign a positive number r_{i}. Now realize each edge e_{ij} joining v_{i} to v_{j} by a Euclidean segment of length

l_{ij} = \sqrt{r_{i}^{2} + r_{j}^{2} + 2r_{i}r_{j} cos(Φ(e_{ij}))}.

Note that, due to Φ(e) ≤ π/2, these positive numbers {l_{ij}, l_{jk}, l_{ki}} satisfy triangle inequalities (see [14, Lemma 13.7.2]). (Also note that if the weight Φ = 0, then l_{ij} = r_{i} + r_{j}. This corresponds to the case that circle patterns come from tangency.) Thus we can realize each triangle Δv_{i}v_{j}v_{k} by a Euclidean triangle of edge lengths l_{ij}, l_{jk}, l_{ki}. The triangle is formed by the centers of three circles of radii r_{i}, r_{j} and r_{k} intersecting at angles Φ(e_{ij}), Φ(e_{jk}) and Φ(e_{ki}) where e_{nm} is the edge joining v_{n} and v_{m}. This produces a flat cone metric on the surface X with singularities at the vertices. We call these metrics the circle-packing metrics (based on (T, Φ)). Let a_{i} be the cone angle at the vertex v_{i} which is the sum of all inner angles having vertex v_{i}. The curvature K_{i} at v_{i} is defined to be 2π − a_{i}. The combinatorial Ricci flow is the following:

\frac{dr_{i}}{dt} = −K_{i}r_{i}. (1.1)

It is easy to show that for any initial circle-packing metric, the solution of (1.1) with the given initial value exists for all time t ≥ 0. Our goal is to understand the asymptotic behavior of the solution. To this end, it is useful to consider the normalized Ricci flow,

\frac{dr_{i}}{dt} = −(K_{i} − K_{av})r_{i} (1.2)

where K_{av} = 1/N ∑_{i=1}^{N} K_{i} is the average curvature. By the Gauss-Bonnet theorem (Proposition 3.1), K_{av} = 2πχ(X)/N is time independent. The two equations (1.1) and (1.2) are related by a change of scales. Namely r_{i}(t) is a solution to (1.1) if and only if e^{2πtχ(X)/N}r_{i}(t) is a solution of (1.2). Furthermore, if r_{i}(t) is a solution to the normalized Equation (1.2), the product ∏_{i=1}^{N} r_{i}(t) is a constant. For this reason, when we consider the asymptotic behavior of the Ricci flow, it is more convenient to deal with the normalized Ricci flow (1.2). Let R_{>0} be the set of all positive real numbers.

Definition. A solution to (1.2) is called convergent if

(1) lim_{t→∞} K_{i}(t) = K_{i}(∞) ∈ (−∞, 2π) exists for all i, and

(2) lim_{t→∞} r_{i}(t) = r_{i}(∞) ∈ R_{>0} exists for all i.

A convergent solution is called convergent exponentially fast if there are positive constants c_{1}, c_{2} so that for all time t ≥ 0,

|K_{i}(t) − K_{i}(∞)| ≤ c_{1}e^{−c_{2}t},

and

|r_{i}(t) − r_{i}(∞)| ≤ c_{1}e^{−c_{2}t}.

Given any subset I ⊂ V, let F_{I} be the set of all cells in T whose vertices are in I and let the link of I, denoted by Lk(I), be the set of pairs (e, v) of an edge e and a vertex v so that (1) the end points of e are not in I and (2) the vertex v is in I and (3) e and v form a triangle.

Theorem 1.1. Suppose (T, Φ) is a weighted triangulation of a closed connected surface X. Given any initial circle-packing metric based on the weighted triangulation, the solution to the normalized combinatorial Ricci flow (1.2) in the Euclidean geometry with the given initial value exists for all time and converges if and only if for any proper subset I ⊂ V,

2π|I|χ(X)/|V | > − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}). (1.3)

Furthermore, if the solution converges, then it converges exponentially fast to the metric of constant curvature 2πχ(X)/N.

By the work of Thurston on circle packing, Condition (1.3) is equivalent to the existence of constant curvature circle packing metric based on the weighted triangulation on the surface.

In the case that the surface has negative Euler characteristic, it is natural to replace Euclidean triangles by the hyperbolic ones. The combinatorial Ricci flow in the hyperbolic geometry is the following: Given a surface X with a weighted triangulation (T, Φ) where Φ(E) ⊂ [0, π/2], we assign to each vertex of T a positive radius r_{i}. We realize each triangle Δv_{i}v_{j}v_{k} by a hyperbolic triangle formed by the centers of three circles of radii r_{i}, r_{j} and r_{k} intersecting at angles Φ(e_{ij}), Φ(e_{jk}) and Φ(e_{ki}). Let a_{i} be the cone angle at v_{i} and K_{i} = 2π − a_{i} be its curvature. The combinatorial Ricci flow in the hyperbolic metric is,

\frac{dr_{i}}{dt} = −K_{i} sinh r_{i}. (1.4)

Theorem 1.2. Suppose (T, Φ) is a weighted generalized triangulation of a closed connected surface X of negative Euler characteristic. Given any initial choice of circle-packing metric, the solution to (1.4) in the hyperbolic background geometry with the given initial value exists for all time and converges if and only if the following two conditions hold:

(1.5a) For any three edges e_{1}, e_{2}, e_{3} forming a null homotopic loop in X, if ∑_{i=1}^{3} Φ(e_{i}) ≥ π, then these three edges form the boundary of a triangle of T.

(1.5b) For any four edges e_{1}, e_{2}, e_{3}, e_{4} forming a null homotopic loop in X, if ∑_{i=1}^{4} Φ(e_{i}) ≥ 2π, then these e_{i}’s form the boundary of the union of two adjacent triangles.

Furthermore, if it converges, then it converges exponentially fast to a hyperbolic metric on X so that all vertex angles are 2π.

Conditions (1.5a) and (1.5b) were obtained by Thurston in his work on circle packing on surfaces. Indeed, according to [14] Theorem 13.7.1, these two conditions are equivalent to the existence of circle packing metric with curvature equal to zero at each vertex.

The following result shows that Condition (1.3) is almost the same as Conditions (1.5a) and (1.5b) for surfaces with nonnegative Euler characteristic.

Proposition 1.3.

(a) If the Euler characteristic of the surface X is positive, then Condition (1.3) is valid for all triangulations of X so that there are no null homotopic loops consisting of 3 edges e_{1}, e_{2}, e_{3} with ∑_{i=1}^{3}Φ(e_{i}) ≥ π.

(b) If the Euler characteristic of the surface X is zero, then (1.3) is valid for all triangulations of X so that (1.5a) and (1.5b) hold.

Note that if the weight is the zero function, the conditions in Theorem 1.2 and Proposition 1.3 automatically hold.

1.3

The exponential convergence of the Ricci flow may have some applications in practice. Recall that in his original proof of the existence of zero curvature circle packing metric, Thurston gave an algorithm to find the circle packing. This algorithm adjusts the radii at vertices one at a time. It is shown in [11] that Thurston’s algorithm converges in polynomial time to the circle packing. To the best of our knowledge, the existing computer softwares (for instance, [13]) are based on Thurston’s algorithm. It seems Ricci flow is more natural and may produce a faster algorithm to find circle packing metrics.

1.4

In the case that the background metric is spherical, we consider triangulations with zero weights. The combinatorial Ricci flow is

\frac{dr_{i}}{dt} = −K_{i} sin r_{i} (1.6)

where we realize each triangle Δv_{i}v_{j}v_{k} by a spherical triangle of edge lengths r_{i} + r_{j}, r_{j} + r_{k}, r_{k} + r_{i} (note that we must impose r_{i} ∈ (0, π) and r_{i} + r_{j} + r_{k} < π in this case). Numerical simulations by L.T. Cheng [2] shows that the situation is very complicated even in the simplest case of triangulations of the 2-sphere, i.e., the boundary of a tetrahedron. For instance, if we start with the boundary of the regular spherical tetrahedron, then the metric will shrink to a point in finite time. If we rescale it to have a fixed area, the cone angles will tend to π (i.e., tends to the boundary of the Euclidean regular tetrahedron if rescaled). But in some other cases, there are initial metrics so that as time goes to a finite number, the metric tends to the round 2-sphere. We do not know what the asymptotic behavior of the solution should be in general.

1.5

The proofs of the above theorems follow the same strategy used by Hamilton in his original approach in the smooth case. Namely, one first derives the evolution equation for the curvature. These equations are essentially of parabolic type. Thus the maximum principle can be applied to control the behaviors of the curvature. In some senses, what we are doing are quantifications of Thurston’s original proof. For instance, the fact that the curvature evolution is a heat equation is essentially a consequence of Thurston’s lemma 13.7.3 in [14]. We also observed the fact that ∂θ_{i}/∂r_{j} sinh(r_{j}) = ∂θ_{j}/∂r_{i} sinh(r_{i}) (for hyperbolic case) and ∂θ_{i}/∂r_{j}r_{j} = ∂θ_{j}/∂r_{i}r_{i} (for Euclidean case) where θ_{i} is the inner angle at i-th vertex corresponding to r_{i} radius circle (Lemma 2.3). This was first observed in the paper of Colin de Verdiere [5] for the zero weighted triangulation. This makes the Ricci flow variational. Namely, it is essentially a gradient flow of a convex function. We observed that the degeneration condition obtained in Thurston’s work implies that the Palais-Smale condition holds for the convex functional. Thus establishes the main results. We remark that the convexity was first observed in [5] in the case of the zero weighted triangulation. Also if a triangulation has zero weight, i.e., Φ = 0, then the convergence part of Theorem 1.2 can also be deduced from the results of Thurston [14] and Colin de Verdiere [5]. Our proofs are different from that of Colin de Verdiere [5]. Colin de Verdiere used a result in network flow to produce the coherent system of angles. From this system, he then produced the convex function and showed that it is proper. In our case, it is the maximum principle and Palais-Smale condition which imply the exponential convergence. Another related work is [1].

1.6

The paper is organized as follows. In §2, we collect some known results concerning triangles. Most of the proofs will be deferred to the appendix. In §3, we derive the evolution equation for the curvature and discuss some of its consequences. In §4, we establish a compactness theorem concerning the solutions of the Ricci flow. In §5, we prove Theorem 1.2. In §6, we prove Theorem 1.1. In the appendix, we derive some basic properties of the triangles.

1.7

The work is supported in part by the NSF DMS 0203926 (at UCSD) and DMS 0103843 (at Rutgers University).

2. Preliminaries on triangles

Let K^{2} be one of the three geometries, E^{2} (Euclidean), S^{2} (spherical) and H^{2} (hyperbolic), i.e., a simply connected surface with a complete Riemannian metric of curvature equal to 0, 1, and -1. For simplicity, we define a function s(x) according the geometry K^{2} as follows. If K^{2} = E^{2}, then s(x) = x; if K^{2} = H^{2}, then s(x) = sinh(x); and if K^{2} = S^{2}, then s(x) = sin(x).

A function is called elementary if it can be obtained from the polynomials, the exponential functions, logarithmic functions, the trigonometric functions and their inverses by the five operations of addition, subtraction, multiplication, division and composition.

2.1

The following lemma of Thurston guarantees the existence of a circle pattern in the geometry K^{2}.

Lemma 2.1 ([14, Lemma 13.7.2]). For any three angles Φ_{i}, Φ_{j}, Φ_{k} ∈ [0, π/2] and any three radii r_{i}, r_{j}, r_{k} ∈ R_{>0}, there exists a configuration of three circles in both Euclidean and hyperbolic geometries, unique up to isometry, having radii r_{i}, r_{j}, r_{k} and meeting in angles Φ_{i}, Φ_{j}, Φ_{k}. Furthermore, if r_{i} + r_{j} + r_{k} < π, then such a configuration of three circles also exists in the spherical geometry S^{2} and is unique up to isometry.

Indeed, let x_{i} be the distance between the centers of the j-th and kth circles. Then it suffices to verify that {x_{i}, x_{j}, x_{k}} satisfies the triangle inequalities that sum of two is larger than the third and also x_{i} + x_{j} + x_{k} < 2π in the case of S^{2}. To see the first, we have x_{i} ≤ r_{j} +r_{k} ≤ x_{j} +x_{k} since Φ_{n} ≤ π/2. Furthermore, the equality x_{i} = x_{j} + x_{k} does not hold. The second inequality follows from x_{i} + x_{j} + x_{k} ≤ 2(r_{i} + r_{j} + r_{k}).

Consider the triangle formed by the centers of the three circles in Lemma 2.1 in K^{2}. Let θ_{i} be the inner angle at the i-th vertex corresponding to the radius r_{i} circle. Then θ_{i} is a smooth function of the radii r_{i}, r_{j}, r_{k}. The following is known in Thurston’s notes:

Lemma 2.2 ([14, Lemma 13.7.3]). In all three geometries E^{2}, H^{2} or S^{2}, if all angles Φ_{n}’s are in [0, π/2], then we have:

(a) ∂θ_{i}/∂r_{i} < 0.

(b) ∂θ_{i}/∂r_{j} > 0 for i ≠ j.

(c) ∂(θ_{i} + θ_{j} + θ_{k})/∂r_{i} < 0 in H^{2}, ∂(θ_{i} + θ_{j} + θ_{k})/∂r_{i} > 0 in S^{2} and ∂(θ_{i} + θ_{j} + θ_{k})/∂r_{i} = 0 in E^{2}.

Furthermore, the partial derivatives ∂θ_{n}/∂r_{m} are elementary functions in r_{i}, r_{j} and r_{k} where n, m ∈ {i, j, k}.

Note part (c) follows from Thurston’s geometric argument that the area of the triangle increases when r_{i} increases. A computational proof of Lemma 2.2 which gives the explicit formulas and the geometric meaning of these partial derivatives can be obtained using Lemma A1 in the Appendix. Also see the proof of Lemma 2.3.

The next lemma was first obtained by Colin de Verdiere [5] in the case where all angles Φ_{n}’s are zero.

Lemma 2.3. In all three geometries E^{2}, H^{2} and S^{2} and for all angles Φ_{i}, Φ_{j}, Φ_{k} ∈ [0, π) so that the triangle of radii r_{i}, r_{j} and r_{k} intersecting at these angles exists,

∂θ_{i}/∂r_{j}s(r_{j}) = ∂θ_{j}/∂r_{i}s(r_{i}).

We defer the proof to the Appendix. In the Appendix, we give two proofs. The simpler proof uses the mathematical software Maple VII.

One consequence of the lemmas is the following:

Proposition 2.4. Suppose all angles Φ_{n} are in [0, π/2]. If the radii r_{n}’s evolve in time according to some differential equation dr_{n}(t)/dt = −K_{n}s(r_{n}) where K_{n} is a function of r_{i}, r_{j} and r_{k} and n = i, j, k, then the evolution of the inner angle θ_{i} satisfies the equation,

dθ_{i}/dt = −A_{ij}(K_{j} − K_{i}) − A_{ik}(K_{k} − K_{i}) − A_{i}K_{i}λ

where A_{rs} for r ≠ s and A_{n} are positive valued elementary functions in r_{i}, r_{j} and r_{k}, λ is the curvature of the geometry K^{2}. Furthermore A_{rs} = A_{sr}.

Proof. By the chain rule, we have

dθ_{i}/dt = ∂θ_{i}/∂r_{i}r′_{i} + ∂θ_{i}/∂_{j}r′_{j} + ∂θ_{i}/∂r_{k}r′_{k}
= −∂θ_{i}/∂r_{i}s(r_{i})K_{i} − ∂θ_{i}/∂r_{j}s(r_{j})K_{j} − ∂θ_{i}/∂r_{k}s(r_{k})K_{k}

= −∂θ_{i}/∂r_{j}s(r_{j})(K_{j} − K_{i}) − ∂θ_{i}/∂r_{k}s(r_{k})(K_{k} − K_{i}) − D_{i}K_{i}.

Here D_{i} = ∂θ_{i}/∂r_{i}s(r_{i}) + ∂θ_{i}/∂r_{j}s(r_{j}) + ∂θ_{i}/∂r_{k}s(r_{k}). By Lemma 2.3, we can write D_{i} as ∑_{l∈{i,j,k}} ∂θ_{l}/∂r_{i}s(r_{i}) = s(r_{i})∂(∑_{l∈{i,j,k}} θ_{l})/∂r_{i}. By Lemma 2.2(c), the last partial derivative is negative in the case K^{2} = H^{2}, is positive in the case K^{2} = S^{2} and is zero if K^{2} = E^{2}. Define A_{i} = λD_{i} when K^{2} = S^{2} or H^{2} and A_{i} = 1 when K^{2} = E^{2}. Then A_{i} > 0. Let A_{mn} = ∂θ_{m}/∂r_{n}s(r_{n}) for n ≠ m. Then by Lemma 2.2, it is positive and is an elementary function. Furthermore, the fact A_{mn} = A_{nm} follows from Lemma 2.3. Thus the result follows.

3. The 2-dimensional combinatorial Ricci flow

3.1 Basic setup and the Gauss-Bonnet formula

We set up the Ricci flow in the most general setting as follows.

Suppose X is a connected compact surface with possibly nonempty boundary. A generalized triangulation T of X is a cell-division of X into cells so that the lifting of the cell-division in the universal cover is a triangulation. In particular, each 2-cell (triangle) lifts to an embedding in the universal cover and there are no vertices of degree 1 or 2. Also there are no null homotopic loops formed by at most 2 edges. Furthermore, given three vertices, there is at most one triangle having them as vertices. The set of all vertices (0-cells), edges (1-cells) and triangles (2-cells) in T are denoted by V, E, F. Unless mentioned otherwise, a weight on the generalized triangulation T is a function Φ : E → [0, π/2]. The pair (T, Φ) is called a weighted generalized triangulation.

This definition of generalized triangulation is slightly different from Theorem 13.7.1 in Thurston’s note. In fact, we were not able to rule out the degree 2 vertices from Thurston’s definition. On the other hand, it is clear that if a triangulation is realized by a circle packing, there cannot be any degree two vertices.

Fix a background geometry K^{2}. Given a compact surface X together with a weighted generalized triangulation (T, Φ), we assign to each vertex v_{i} ∈ V = {v_{1}, …, v_{N}} a positive number r_{i}. If the geometry K^{2} is spherical S^{2}, we assume that r_{i} + r_{j} + r_{k} < π holds for all triples {r_{i}, r_{j}, r_{k}} so that the corresponding vertices form a triangle in T.

For each triangle Δv_{i}v_{j}v_{k} in F having edges e_{ij}, e_{jk} and e_{ki}, using Lemma 2.1 we can realize the triangle as the one formed by the centers of the three circles of radii r_{i}, r_{j}, r_{k} meeting in angles Φ(e_{ij}) , Φ(e_{jk}) and Φ(e_{ki}) in geometry K^{2}. This produces a Riemannian metric on the surface X of constant curvature having singularities at the vertices. Let a_{i} be the sum of all inner angles having vertex v_{i} in triangles. Then the curvature at v_{i} is defined to be K_{i} = 2π − a_{i} when the vertex v_{i} is in the interior of X and K_{i} = π − a_{i} when v_{i} is in the boundary.

Our first observation is the following:

Proposition 3.1 (Gauss-Bonnet). Let λ = −1, 0, 1 be the curvature of one of the three geometries H^{2}, E^{2}, S^{2} used in the construction. If the circle packing metric based on a weighted generalized triangulation (T, Φ) exists where Φ : E → [0, π), then the total curvature

∑_{i=1}^{N} K_{i} = 2πχ(X) − λArea (X).

Note that the three terms in the Gauss-Bonnet formula are additive with respect to gluing along the surface boundary. Thus by doubling the surface X across the boundary if X has nonempty boundary, it suffices to show the result for compact surfaces X without boundary. If X has no boundary, let θ_{i}^{jk} be the inner angle of the triangle Δv_{i}v_{j}v_{k} at v_{i} (θ_{i}^{jk} is defined to be zero if v_{i}, v_{j}, v_{k} do not form a triangle). Then the area A_{ijk} of Δv_{i}v_{j}v_{k} satisfies the equation,

θ_{i}^{jk} + θ_{j}^{ik} + θ_{k}^{ki} = π + λA_{ijk}.

Since a_{i} = ∑_{j,k} θ_{i}^{jk}, we have

∑_{i} K_{i} = 2πN − ∑_{i,j,k} θ_{i}^{jk}

= 2πN − ∑_{Δv_{i}v_{j}v_{k}}(θ_{i}^{jk} + θ_{j}^{ik} + θ_{k}^{ki})

= 2πN − π|F | − λArea (X) = 2πχ(X) − λArea (X).

As a consequence, if K^{2} = E^{2}, then the average curvature of a circlepacking metric is 2πχ(X)/N. In particular, the constant curvature metric has curvature 2πχ(X)/N.

3.2 The combinatorial Ricci flow

We define the combinatorial Ricci flow (with background metric K^{2}) to be

dr_{i}(t)/dt = −K_{i}s(r_{i}(t)). (3.1)

The evolution of curvature was first obtained by He [9] for zero weighted triangulations in Euclidean geometry.

Proposition 3.2. Under the Ricci flow (3.1), the curvature K_{i}(t) evolves according to

dK_{i}/dt = ∑_{j∼i} C_{ij}(K_{j} − K_{i}) + λB_{i}K_{i} (3.2)

where the sum is over all vertices v_{j} adjacent to v_{i}, C_{ij} and B_{i} are positive elementary functions in the radii r_{1}, ..., r_{N}. Furthermore, C_{ij} = C_{ji}.

This is a direct consequence of Proposition 2.4 since

dK_{i}/dt = − ∑_{j,k} dθ_{i}^{jk}/dt

where θ_{i}^{jk} are inner angles at v_{i} in the triangle Δv_{i}v_{j}v_{k}.

As a consequence, we obtain the maximum principle for curvature evolutions.

Corollary 3.3 (The Maximum Principle). Let r(t) = (r_{1}(t), …, r_{N}(t)) be a solution of the Ricci flow (3.1) in an interval. Let M(t) = max{K_{1}(t), …, K_{N}(t)} and m(t) = min{K_{1}(t), …, K_{N}(t)}.

(1) In the case of Euclidean geometry E^{2}, then the function M(t) is non-increasing in t and m(t) is non-decreasing in time t.

(2) In the case of hyperbolic geometry H^{2}, then max(M(t), 0) is nonincreasing in t and min(m(t), 0) is non-decreasing in time t.

3.3 The long time existence of solutions

As a consequence of the maximum principle, we have,

Proposition 3.4. Suppose the background geometry K^{2} is E^{2} or H^{2}. For any initial metric r(0) ∈ R_{>0}^{N}, the solution to the Ricci flow (3.1) with the given initial metric exists for all time t ≥ 0.

Indeed, we note first of all the curvature K_{i} is always bounded, i.e.,

(2 − d)π < K_{i} < 2π

where d is the degree of the vertex v_{i}.

In the case of Euclidean geometry E^{2}, by (3.1), we obtain

c_{1}e^{(2−d)πt} ≤ r_{i}(t) ≤ c_{2}e^{2πt}

for some positive constants c_{1} and c_{2}. Thus r_{i}(t) remains bounded above and away from zero as long as t is bounded. This implies that the Ricci flow (3.1) has a solution for all time t ≥ 0 for any initial value r(0) ∈ R_{>0}^{N}.

In the case of H^{2}, since K_{i}(t) = d(ln(coth(r_{i}/2)))/dt, we obtain

coth r_{i}/2 ≤ ce^{2πt}

where c is some constant. Thus r_{i}(t) remains bounded away from 0 as long as time t is bounded. On the other hand, the maximum principle (Corollary 3.3) shows that r_{i}(t) is bounded from above as well. To see this, we first have:

Lemma 3.5. For any ϵ > 0, there exists a number L so that when r_{i} > L, the inner angle θ_{i} in the hyperbolic triangle Δv_{i}v_{j}v_{k} is smaller than ϵ.

This is a simple fact from hyperbolic geometry. Indeed, if we put v_{i} in the Euclidean center of the disk model for the hyperbolic plane and choose a large radius circle centered at v_{i} in the hyperbolic space, then the Euclidean diameters of the other two circles centered at v_{j} and v_{k} can be made very small. Thus the angle at v_{i} can be made arbitrary small if the radius r_{i} is large.

As a consequence of the lemma, if there exists a sequence of times t_{n} → a where a ∈ (0, ∞] so that r_{i}(t_{n}) tends to infinity, then K_{i}(t_{n}) will tend to 2π. This contradicts the non-increasing property of the function M(t) < 2π.

By combining the above two, we see that as long as time remains bounded, then r_{i}(t) and 1/r_{i}(t) remain bounded. This implies that the solution to (3.1) exists for all time t ≥ 0.

As a consequence of Lemma 3.5 and the maximum principle, we have:

Corollary 3.6. Suppose r(t) (t ≥ 0) is a solution to the Ricci flow (3.1) in hyperbolic background geometry, then there exists a constant C so that r_{i}(t) ≤ C for all time t ≥ 0 and all indices i.

3.4 An existence theorem in the hyperbolic and Euclidean cases

The following proposition shows that it suffices to establish a compactness result in order to show the long time convergence of the solution to (3.1).

Proposition 3.7. Suppose r(t) for t ∈ [0, ∞) is a solution to the Ricci flow (3.1) in H^{2} geometry so that the set {r(t)|t ∈ (0, ∞)} lies in a compact region in R_{>0}^{N}. Then r(t) converges exponentially fast to a circle packing metric in R_{>0}^{N} whose curvature at each vertex is zero.

Proof. Since the coefficient B_{i} in (3.2) is an elementary function in r_{1}, …, r_{N} and is always positive, it follows from the assumption that there exist two positive constants c_{1} and c_{2} so that

c_{1} ≤ B_{i}(r_{1}(t), …, r_{N}(t)) ≤ c_{2}

for all time t ≥ 0. Let M_{∗}(t) = max(M(t), 0) and m_{∗}(t) = min(m(t), 0). By Equation (3.2), we obtain

dM_{∗}(t)/dt ≤ −c_{1}M_{∗}(t)

and

dm_{∗}(t)/dt ≥ −c_{2}m_{∗}(t).

Thus there are two constants c_{3} > 0 and c_{4} > 0 so that

c_{5}e^{−c_{3}t} ≤ m_{∗}(t) ≤ M_{∗}(t) ≤ c_{6}e^{−c_{4}t}.

This shows that the curvature K_{i}(t) converges exponentially fast to zero. This in turn implies that ∫_{0}^{t} K_{i}(s)ds converges exponentially fast to some constant. Since (3.1) says coth(r_{i}(t)/2) = ce^{∫_{0}^{t} K_{i}(s)ds}, it follows that lim_{t→∞} r_{i}(t) = R_{i} exists in R_{>0} and r_{i}(t) converges to R_{i} exponentially fast. Thus the result follows. q.e.d.

The same proposition also works for the Euclidean case. In this case, we should normalize the equation. By the Gauss-Bonnet theorem, the sum of the curvatures is 2πχ(X). Thus the average curvature K_{av} is 2πχ(X)/N which is independent of time t. We define the normalized Ricci flow to be

dr_{i}(t)/dt = −(K_{i} − K_{av})r_{i} (3.3)

It is easy to verify that r(t) solves (3.3) for K^{2} = E^{2} if and only if e^{K_{av}t}r(t) solves (3.3).

Proposition 3.8. Suppose r(t) for t ∈ (0, ∞) is a solution to the normalized Ricci flow (3.3) in E^{2} so that the set {r(t)|t ∈ (0, ∞)} lies in a compact region in R_{>0}^{N}. Then r(t) converges exponentially fast to a circle packing metric in R_{>0}^{N} whose curvature at each vertex is the average curvature K_{av}.

Proof. To show that the metrics r(t) = (r_{1}(t), …, r_{N}(t)) converge exponentially to a vector in R_{>0}^{N}, by the same argument as in the proof of Proposition 3.7, it suffices to show that the curvatures K(t) = (K_{1}(t), …, K_{N}(t)) converges exponentially fast to K_{av}(1, …, 1). To this end, let us consider the function g(t) = ∑_{i=1}^{N}(K_{i}(t) − K_{av})^{2}. Since ∑_{i=1}^{N} K_{i} = NK_{av}, we have g(t) = ∑_{i=1}^{N} K_{i}^{2} − NK_{av}^{2}. Thus the derivative g′(t) = 2 ∑_{i=1}^{N} K_{i}(t)K′_{i}(t). By Proposition 2.4 and dK_{av}/dt = 0, the evolution equation for the curvature K_{i}(t) satisfies the following:

K′_{i}(t) = ∑_{j∼i} C_{ij}((K_{j} − K_{av}) − (K_{i} − K_{av}))

= ∑_{j∼i} C_{ij}(K_{j} − K_{i}),

where C_{ij} = C_{ji} is positive and is an elementary function in r_{1}, …, r_{N}. Thus

g′(t) = 2 ∑_{i=1}^{N} ∑_{i∼j} C_{ij}K_{i}(K_{j} − K_{i}).

By switching the order of i, j, we also have

g′(t) = 2 ∑_{j=1}^{N} ∑_{j∼i} C_{ji}K_{j}(K_{i} − K_{j}).

Thus

g′(t) = − ∑_{i∼j} C_{ij}(K_{i} − K_{j})^{2} (3.4)

where the sum is over all pairs of adjacent vertices v_{i} and v_{j}. Since the metrics r(t) lies in a compact region in R_{>0}^{N}, the coefficients C_{ij}(r_{1}(t), …, r_{N}(t)) remain bounded for all time t ≥ 0, i.e., C_{ij} ≥ c_{1} > 0 for some constant c_{1}.

Claim. There exists a constant c_{2} > 0 depending only on the triangulation T so that

c_{2} ∑_{i=1}^{N}(K_{i} − K_{av})^{2} ≤ ∑_{i∼j} C_{ij}(K_{i} − K_{j})^{2}

for all time t ≥ 0.

Assuming the Claim, by (3.4), we obtain the following:

g′(t) ≤ −c_{2}g(t).

This implies that g(t) ≤ c_{3}e^{−c_{2}t} for all time t ≥ 0 for some constant c_{3}. In particular, we obtain |K_{i}(t) − K_{av}|^{2} ≤ g(t) ≤ c_{3}e^{−c_{2}t}. Thus the proposition holds.

To see the Claim, we first note that since C_{ij} are uniformly bounded from below, it suffices to prove that

∑_{i=1}^{N}(K_{i} − K_{av})^{2} ≤ c_{4} ∑_{i∼j}(K_{i} − K_{j})^{2} (3.5)

for some constant c_{4}. By Cauchy’s inequality that for any sequence {a_{i}}

(a_{i} − \frac{∑_{j=1}^{N} a_{j}}{N} )^{2} ≤ 1/N (∑_{j=1}^{N}(a_{i} − a_{j})^{2}) ,

we obtain

∑_{i=1}^{N}(K_{i} − K_{av})^{2} ≤ 1/N ∑_{i,j=1}^{N}(K_{i} − K_{j})^{2}.

On the other hand, since the surface X is connected, for any two vertices v_{i} and v_{j} in T, there exists a sequence of vertices v_{m_{1}} = v_{i}, v_{m_{2}}, …, v_{m_{l}} = v_{j} so that v_{m_{h}} and v_{m_{h+1}} are adjacent. We can estimate the value (K_{i} − K_{j})^{2} in terms of the sum of adjacent terms (K_{m_{h}} − K_{m_{h+1}})^{2}. This shows that there exists a constant c_{5} depending only on T so that (K_{i} − K_{j})^{2} ≤ c_{5} ∑_{l∼m}(K_{l} − K_{m})^{2}. Thus

∑_{i,j=1}^{N}(K_{i} − K_{j})^{2} ≤ c_{5}N ∑_{i∼j}(K_{i} − K_{j})^{2}.

Combining all these, we establish the claim. Thus the proposition follows.

3.5 The Ricci flow is variational

In this section, we establish the fact that the combinatorial Ricci flow is essentially the gradient flow of a function. In the case that the background geometry is E^{2} or H^{2}, the function is convex.

Let u_{i} be a function of r_{i} so that du_{i}/dr_{i} = 1/s(r_{i}). To be more precise, we choose u_{i} = ln r_{i} when K^{2} = E^{2}, u_{i} = ln tanh(r_{i}/2) in K^{2} = H^{2} and u_{i} = ln tan(r_{i}/2) when K^{2} = S^{2}. Let U be the following open set: If K^{2} = E^{2}, then U = R^{N}; if K^{2} = H^{2}, then U = (−∞, 0)^{N}. In the case of the spherical geometry, we take U to be the inverse image of all possible r = (r_{1}, …, r_{N}) under the map (u_{1}, …, u_{N}) → (r_{1}, …, r_{N}).

Under this change of variable, the Ricci flow (3.1) takes the following form:

du_{i}/dt = −K_{i}. (3.6)

Indeed, (3.6) is a gradient flow in the variable u. To see this, by Lemma 2.3, we have ∂K_{i}/∂r_{j}s(r_{j}) = ∂K_{j}/∂r_{i}s(r_{i}). This is equivalent to ∂K_{i}/∂u_{j} = ∂K_{j}/∂u_{i}. Thus the 1-form ∑_{i=1}^{N} K_{i}du_{i} is closed in the simply connected space U. Define a function f(u) = ∫_{a}^{u} ∑_{i=1}^{N} K_{i}du_{i} where a is any point in U. Then we have ∂f(u)/∂u_{i} = K_{i}. This shows that (3.6) is the negative gradient flow of the function f. We remark that a family of functionals like this f was first constructed by Colin de Verdiere in his paper [5] in the case the weight function is zero. Colin de Verdiere also first proved the convexity of f in the zero weight case.

Proposition 3.9.

(a) If K^{2} = H^{2}, then the function f(u) : U → R is strictly convex.

(b) If K^{2} = E^{2}, then the function f(u) : U → R is convex. Furthermore, it satisfies f(u + a(1, 1, …, 1)) = f(u) for all a and f is strictly convex when restricted in the plane

P = {(u_{1}, …, u_{N}) | ∑_{i=1}^{N} u_{i} = 0} .

Proof. Let us consider the hessian of the function f.

Let a_{ij} = ∂^{2}f/∂u_{i}∂u_{j} = ∂K_{i}/∂u_{j}. By Lemma 2.2, we have a_{ii} > 0 and a_{ij} ≤ 0 ( a_{ij} < 0 if v_{i} is adjacent to v_{j}). Furthermore, Lemmas 2.2 and 2.3 show that if K^{2} = H^{2}, then ∂θ_{i}/∂r_{i} sinh(r_{i})+∂θ_{i}/∂r_{j} sinh(r_{j})+ ∂θ_{i}/∂r_{k} sinh(r_{k}) < 0. Now sum over all such inequalities at the i-th vertex and use the fact that a_{ij} = − ∑_{r,s} ∂θ_{i}^{rs}/∂r_{j} sinh(r_{j}), we obtain ∑_{j=1}^{N} a_{ij} > 0. Recall a simple fact from linear algebra:

Lemma 3.10. Suppose A = [a_{ij}]_{n×n} is a symmetric matrix.

(a) If a_{ii} > ∑_{j≠i} |a_{ij}| for all indices i, then A is positive definite

(b) If a_{ii} > 0 and a_{ij} ≤ 0 for all i ≠ j so that ∑_{i=1}^{n} a_{ij} = 0 for all j, then A is semi-positive definite so that its kernel is onedimensional.

Thus Part (a) of the proposition follows.

To see Part (b) of the proposition, note that Lemmas 2.2 and 2.3 show that a_{ii} > 0, a_{ij} ≤ 0 and ∑_{i=1}^{N} a_{ij} = 0. By the linear algebra fact above, this implies that the matrix [a_{ij}] is semi-definite. Thus f is convex in R^{n}. The identity f(u + (a, a, …, a)) = f(u) follows from the fact that K_{i}(ar) = K_{i}(r). The last fact that f|_{P} is strictly convex follows from the linear algebra consideration, namely, the kernel of the matrix [a_{ij}]_{N×N} is generated by the vector (1, 1, …, 1).

To prove Lemma 3.10 (a), it suffices to show that det(A) > 0, since the same argument will show that all determinants of the principle submatrices of A are positive. This in turn implies that A is positive definite. Now to show det(A) > 0, we first show that det(A) ≠ 0. This follows easily from the given condition. For instance, if (x_{1}, …, x_{n}) were a nonzero vector so that ∑_{j} a_{ij}x_{j} = 0 for all i, take x_{k} to be the coordinate with the maximum absolute value. Now consider ∑_{j=1}^{n} a_{kj}x_{j} = 0. We obtain a_{kk}|x_{k}| = | ∑_{i≠k} a_{ki}x_{i}|. But this contradicts the assumptions that a_{kk} > ∑_{i≠k} |a_{ki}| and |x_{k}| ≥ max_{i}{|x_{i}|}. Next multiply all off diagonal entries of A by a constant t so that |t| ≤ 1 to get a new matrix B(t). The matrix B(t) satisfies the same conditions that A satisfies, thus det(B(t)) ≠ 0. But det(B(0)) > 0, thus det(B(t)) > 0. In particular det(A) = det(B(1)) > 0.

To see Part (b) of the lemma, first of all it is clear that [a_{ij}] is semipositive definite (since if we replace a_{ii} by a_{ii} + s for a small positive number s, it becomes positive definite by Part (a)). Thus all eigenvalues of it are nonnegative. Now it is easy to see that the kernel is onedimensional spanned by (1, 1, …, 1). Thus the result follows. q.e.d.

Given a smooth strictly convex function defined on an open convex set D, the gradient map sending a point in D to the gradient of f at the point is always injective. Thus as a consequence of the above proposition, we obtained a new proof of the uniqueness part of Thurston’s theorem.

Corollary 3.11 ([14]). Let Π : R_{>0}^{N} → R^{N} be the map sending a metric (r_{1}, …, r_{N}) to the corresponding curvature (K_{1}, …, K_{N}) where K^{2} = H^{2} or E^{2}. Then:

(a) In the hyperbolic background geometry, Π is injective, i.e., the metric is determined by its curvature.

(b) In the Euclidean geometry, Π restricted to the subset {(r_{1}, …, r_{N}) ∈ R_{>0}^{N}|Π_{i=1}^{N}r_{i} = 1} is injective, i.e., the metric is determined by its curvature up to a scalar multiplication.

4. Degeneration of circle packing metrics

We will recall a related work of [14]. For completeness a slightly different proof is presented. The proof below follows closely [10]. For simplicity, if I = {r_{j}, … r_{l}} is a subset of vertices V, we will also use I to denote the index set {j, …, l}.

Proposition 4.1 ([14]). Suppose (T, Φ) is a weighted generalized triangulation of a closed surface X and I is a subset of vertices V. Here the weight is a map Φ : E → [0, π). Let r^{(n)} = (r_{1}^{(n)}, …, r_{N}^{(n)}) be a sequence of circle packing metrics based on (T, Φ) in background geometry K^{2} so that lim_{n→∞} r_{i}^{(n)} = 0 for i ∈ I and lim_{n→∞} r_{i}^{(n)} > 0 for i ∉ I. Then

lim_{n→∞} ∑_{i∈I} K_{i}(r^{(n)}) = − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}),

where F_{I} is the CW-subcomplex consisting of cells whose vertices are in I and Lk(I) = {(e, v)|e is an edge so that e ∩ I = ∅ and the vertex v ∈ I so that e, v form a triangle}.

Furthermore, if the weight Φ : E → [0, π/2] and the background geometry is E^{2} or H^{2}, then for any circle packing metric r based on (T, Φ) and any proper subset I of vertices V, we have

∑_{i∈I} K_{i}(r) > − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}).

Proof. Recall that θ_{i}^{jk} denotes the inner angle at v_{i} in the triangle Δv_{i}v_{j}v_{k}. Let X̃ → X be the universal cover. Consider triangles in T having a vertex in I. These triangles can be classified into three types A_{1}, A_{2} and A_{3} where a triangle Δ is in A_{i} if and only if a lift of it in the universal cover has exactly i many vertices in π^{−1}(I). (Note that in the surface X, there may be triangles having all vertices being v_{i}.)

Now the curvature K_{i} = 2π − a_{i} where a_{i} is the cone angle at v_{i}. Here ∑_{i∈I} a_{i} can be written as

∑_{v_{i}∈I,Δv_{i}v_{j}v_{k}∈A_{1}} θ_{i}^{jk}+ ∑_{v_{i},v_{j}∈I,Δv_{i}v_{j}v_{k}∈A_{2}}(θ_{i}^{jk}+θ_{j}^{ik})+ ∑_{Δv_{i}v_{j}v_{k}∈A_{3}}(θ_{i}^{jk}+θ_{j}^{ik}+θ_{k}^{ij}).

It is known that as the radius r_{i}^{(n)} tends to zero, the following hold:

(1) If Δv_{i}v_{j}v_{k} ∈ A_{3}, then lim_{n→∞}(θ_{i}^{jk}(r^{(n)})+θ_{j}^{ik}(r^{(n)})+θ_{k}^{ij}(r^{(n)})) = π. Indeed, the triangle is shrinking to a point in K^{2} and thus is becoming a Euclidean triangle.

(2) If Δv_{i}v_{j}v_{k} ∈ A_{2} and i, j ∈ I, then lim_{n→∞}(θ_{i}^{jk}(r^{(n)}) + θ_{j}^{ik}(r^{(n)})) = π. Indeed, the triangle degenerates to a geodesic segment.

(3) If Δv_{i}v_{j}v_{k} ∈ A_{1} and i ∈ I, then lim_{n→∞} θ_{i}^{jk}(r^{(n)}) = π − Φ(v_{j}v_{k}) by definition. Here v_{j}v_{k} ∈ Lk(I).

To summary, we obtain

lim_{n→∞} ∑_{i∈I} K_{i}(r^{(n)}) = − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2π(|I| − 1/2|A_{2}| − 1/2|A_{3}|).

Here |A_{i}| denotes the number of triangles of type A_{i}. Note |A_{3}| is the number of 2-cells in F_{I} and |I| is the number of 0-cells in F_{I}. By the construction, we see that the number of edges in F_{I} is 1/2(|A_{2}|+3|A_{3}|). Thus |I| − 1/2|A_{2}| − 1/2|A_{3}| is the Euler characteristic of F_{I}. This ends the proof.

To see the second part of the proposition, we note that since the background geometry is H^{2} or E^{2}, the sum of the inner angles of a triangle is at most π. Thus, in the first limit (1) above, π is the maximal value. By the same argument, in the second limit (2) above, π is again the maximal value which is never achieved by a nondegenerate triangle. In the third limit (3), since Φ(e) ≤ π/2, using Lemma 2.1 on the monotonicity, we see that π−Φ(v_{j}v_{k}) is also the maximal value for all possible circle packing metrics based on (T, Φ). Furthermore, since I ≠ V, Cases (2) or (3) do occur. This shows that − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}) is strictly less than the sum of the curvature ∑_{i∈I} K_{i}(r) for any circle packing metric based on (T, Φ). q.e.d.

Remark. The proof works for all CW -cell decompositions so that each cell has 3 vertices and each vertex has degree at least 2.

Corollary 4.2. Make the same assumption as in Proposition 4.1 and assume that the weight Φ : E → [0, π/2]. Suppose

− ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}) > 0.

Then one of the following must hold:

(a) There exists a null homotopic loop consisting of 3 edges e_{1}, e_{2}, e_{3} so that ∑_{i=1}^{3} Φ(e_{i}) > π. Furthermore, if X ≠ S^{2}, then these 3 edges do not form the boundary of a triangle.

(b) X = S^{2} and I = V − {v} for one vertex v.

Indeed, choose I′ be the nonempty subset of I of the smallest cardinality so that − ∑_{(e,v)∈Lk(I)}(π−Φ(e))+2πχ(F_{I}) > 0. In this case, F_{I′} is connected since the quantity is additive with respect to connected components of F_{I}. Thus χ(F_{I′}) ≤ 1 so that the equality holds if and only if F_{I′} is contractible. Since − ∑_{(e,v)∈Lk(I′)}(π − Φ(e)) ≤ 0, we see that χ(F_{I′}) = 1 and F_{I′} is contractible. Let e_{1}, …, e_{k} be the set of all edges in Lk(I′). They form a null homotopic loop due to the contractibility of F_{I′}. Now if Lk(I′) ≠ ∅, then ∑_{(e,v)∈Lk(I′)}(π − Φ(e)) ≥ k/2π. Thus k = 3. Note k = 1, 2 are ruled out by the assumption on the generalized triangulation T. If these three edges form the boundary of a triangle, then F_{I′} must be the complement of the triangle. Thus X = S^{2}.

If Lk(I′) = ∅, then V − I′ must consists of vertices so that no two of these vertices are adjacent. On the other hand, F_{I′} is contractible. Thus V − I′ consists of only one point. Thus we see that X is a union of two contractible sets and X = S^{2}.

Corollary 4.3. Make the same assumption as in Proposition 4.1 and assume that the weight Φ : E → [0, π/2]. If there are no subsets of V satisfying the condition in Corollary 4.2 and if

− ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}) = 0,

then one of the following must hold:

(a) There exists a null homotopic loop consisting of k = 3 or 4 edges e_{1}, …, e_{k} so that ∑_{i=1}^{k} Φ(e_{i}) = (k −2)π. Furthermore, if X ≠ S^{2}, then these k edges do not form the boundary of a triangle, or union of two adjacent triangles.

(b) X = S^{2} and I = V − {v, v′} for two non-adjacent vertices v, v′.

(c) X = RP^{2} and I = V − {v}.

Let I′ be the subset of the smallest cardinality so that

∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}) = 0.

By the assumption, we conclude that F_{I′} is connected. Thus χ(F_{I′}) ≤ 1. By the hypothesis, χ(F_{I′}) ≥ 0. If χ(F_{I′}) = 1, then by the given hypothesis, F_{I′} ≠ ∅. By the same argument as above, we obtain conclusion (a). If χ(F_{I}) = 0, then Lk(I′) = ∅, i.e., V − I′ consists of vertices so that no two of them are adjacent. But F_{I′} is either the annulus or the Möbuis band. This shows that either X = S^{2} and I′ = V − {v, v′} where v, v′ are not adjacent or X = RP^{2} and I′ = V − {v}.

Corollary 4.4. Suppose X is a closed surface of negative Euler characteristic and (T, Φ) is a generalized triangulation on X so that the Conditions (1.5a) and (1.5b) in Theorem 1.2 hold. If r^{(n)} ∈ R_{>0}^{N} is a sequence of circle packing metrics in the hyperbolic background metric based on (T, Φ) so that lim inf_{n→∞}K_{i}(r^{(n)}) ≥ 0 and lim sup_{n→∞} K_{i}(r^{(n)}) < 2π for all indices i, then r^{(n)} contains a convergent subsequence in R_{>0}^{N}.

Indeed, by Lemma 3.5 and lim sup_{n→∞} K_{i}(r^{(n)}) < 2π, we see that r_{i}^{(n)} is bounded from above. To see that {r_{k}^{(n)}} is bounded away from 0, suppose otherwise that it contains a subsequence {r_{k}^{(n_{j})}} converging to zero. Let I be the nonempty subset of indices so that lim_{j→∞} r_{i}^{(n_{j})} = 0 for i ∈ I and lim_{j→∞} r_{i}^{(n_{j})} > 0 for i ∉ I. Since lim inf_{j→∞}K_{i}(r^{(n_{j})}) ≥ 0 for all indices i, we obtain lim_{j→∞} ∑_{i∈I} K_{i}(r^{(n_{j})}) ≥ 0. By Corollaries 4.2 and 4.3, we see that one of the conditions (1.5a), (1.5b) in Theorem 1.2 must be false. This contradicts the assumption.

5. A proof of Theorem 1.2

We will prove the following result which is slightly more general than Theorem 1.2.

Theorem 5.1. For any weighted generalized triangulation (T, Φ) of a closed connected surface X of negative Euler characteristic and any initial choice of circle-packing metric, the solution to (1.4) with the given initial value exists for all time and converges if and only if the following two conditions hold:

(1.5a) For any three edges e_{1}, e_{2}, e_{3} forming a null homotopic loop in X, if ∑_{i=1}^{3} Φ(e_{i}) ≥ π, then these three edges form the boundary of a triangle of T.

(1.5b) For any four edges e_{1}, e_{2}, e_{3}, e_{4} forming a null homotopic loop in X, if ∑_{i=1}^{4} Φ(e_{i}) ≥ 2π, then these e_{i}’s form the boundary of the union of two adjacent triangles.

Furthermore, if it converges, then it converges exponentially fast to a hyperbolic metric on X without any singularity.

Note that if the weight Φ is zero, then Conditions (1.5a) and (1.5b) hold automatically. Thus the above result implies the result of Andreev-Koebe-Thurston that for any triangulation of a closed surface of negative Euler characteristic, there exists a hyperbolic metric on the surface and a tangential circle packing in the metric so that the combinatorial pattern of tangency is given by the triangulation.

The proof of the theorem goes in two steps. In the first step, we give a new proof of Thurston’s existence of circle packing metric using Ricci flow. This implies that the strictly convex function f whose negative gradient is du_{i}/dt = −K_{i} where u_{i} = ln tanh(r_{i}/2) has a critical point. In particular, this implies that the function f is bounded from below. On the other hand, Corollary 4.4 shows that the function f satisfies the Palais-Smale condition. Thus the negative gradient flow of f converges to the critical point of f. Combining this with Proposition 3.7, we see that all gradient lines converge exponentially fast to the critical point.

5.1

In this subsection, we produce a new proof of the existence of the zero curvature circle packing metric based on the weighted generalized triangulation (T, Φ).

To begin, let us choose the initial metric r(0) = (r_{1}(0), …, r_{N}(0)) with all r_{i}(0) sufficiently large so that its curvature at v_{i} is close to 2π. This is possible by Lemma 3.5. In particular, we have k_{i}(0) ≥ 0. Let r(t) = (r_{1}(t), …, r_{N}(t)) (t ≥ 0) be a solution to the Ricci flow (3.1) in H^{2} background metric with the initial value r(0). Then by the maximum principle Corollary 3.3, we have k_{i}(t) ≥ 0 for all time t ≥ 0. On the other hand, by the maximum principle again we have lim sup_{t→∞} k_{i}(t) < 2π. Thus by Corollary 4.4, we see that the set {r(t)|t ∈ [0, ∞)} lies in a compact region in R_{>0}^{N}. Thus by Proposition 3.7, the solution r(t) converges exponentially fast to the zero curvature metric. In particular, this shows the zero curvature metric exists.

5.2

To show the convergence of the Ricci flow (3.1) in H^{2} background metric in the general case, we use the result in Subsection 3.5. Recall that if we consider the change of variable u_{i} = ln tanh(r_{i}/2), then the Ricci flow becomes du_{i}/dt = −K_{i} which is proved to be a negative gradient flow. Let f be a potential function. It is known by Proposition 3.9 that the function f is strictly convex defined on (−∞, 0)^{N}. We claim that f satisfies the Palais-Smale condition. As a consequence, we see all gradient lines converge to the critical point. Thus the result follows.

To verify the Palais-Smale condition, first of all by §5.1, we see that f has a critical point which must be the minimal point due to the convexity. Thus f is bounded from below. To verify the second condition in Palais-Smale, take a sequence of points {u^{(n)}} in (−∞, 0)^{N} so that the gradient of f at u^{(n)} converges to zero. Let the corresponding points of u^{(n)} be r^{(n)} ∈ R_{>0}^{N}. Then we have that the curvature K_{i}(r^{(n)}) tends to zero for all indices i as n tends to infinity. By Corollary 4.4, this implies that the set {r^{(n)}|n ∈ Z_{>0}} lies in a compact set. This in turn implies that {u^{(n)}} contains a convergent subsequence in (−∞, 0)^{N}. This ends the proof.

Finally the necessity of Conditions (1.5a) and (1.5b) which was proved in [14] follows from Proposition 4.1. Indeed, since the zero curvature metric exists, we conclude that for any subset I ∈ V, the quantity − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}) < 0. On the other hand, if (1.5a) or (1.5b) is false, then take I to be the vertices in the disk bounded by the null homotopic loop formed by the edges. We see that − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2π(χ(F_{I})) ≥ 0.

Remark 5.3. The proof in fact shows the following for a generalization of the Ricci flow in hyperbolic background metric. Namely, suppose there exists a circle packing metric R so that its curvature is C_{i} at the i-th vertex. Then the following flow dr_{i}/dt = −(K_{i} − C_{i}) sinh(r_{i}) has a solution for all time t ≥ 0 for all initial metrics and the solution converges exponentially fast to R.

6. A proof of Theorem 1.1 and Proposition 1.3

We will prove the following theorem for generalized triangulations which implies Theorem 1.1.

Theorem 6.1. For any weighted generalized triangulation T of a closed connected surface X and for any initial circle-packing metric based on the weighted triangulation, the solution to the normalized combinatorial Ricci flow (1.2) in Euclidean background metric with the given initial value converges if and only if for any proper subset I ⊂ V,

(1.3)  2πχ(X)|I|/N > − ∑_{(e,v)∈Lk(I)}(π − Φ(e)) + 2πχ(F_{I}).

Furthermore, if the solution converges, it converges exponentially fast to the metric of constant curvature 2πχ(X)/N.

The proof is essentially the same as in §5 and goes in two steps. In the first step, we show that the constant curvature circle packing metric exists due to Condition (1.3). Next we show that the normalized Ricci flow is the negative gradient flow of a convex function in the variable u_{i} = ln r_{i} and that the function f satisfies the Palais-Smale condition. Combining this with Proposition 3.7, we see that all gradient lines converge exponentially fast to the critical point.

6.1

In this subsection, we produce a proof of the existence of the constant curvature circle packing metric based on the weighted generalized triangulation (T, Φ) under Condition (1.3). This result is implicitly in [14]. Our proof follows the work [10]. Let P be the set {r = (r_{1}, …, r_{N}) ∈ R_{>0}^{N}| ∏_{i=1}^{N} r_{i} = 1}. Consider the curvature map Π : P → R^{N} sending the metric r to its curvature Π(r) = (K_{1}(r), …, K_{N}(r)). By Corollary 3.11, it is injective. Furthermore, by Gauss-Bonnet, its image lies in the hyperplane defined by the equation ∑_{i=1}^{N} K_{i} = 2πχ(X). Consider the convex polytope Y in the hyperplane defined by the set of all linear inequalities ∑_{i∈I} K_{i} > − ∑_{i∈I}(π − Φ(e)) + 2πχ(F_{I}) where I is a proper subset of vertices. Then by Proposition 4.1 the map Π : P → Y sends compact sets to compact sets. Since both P and Y are homeomorphic to R^{N−1}, by the invariance of domain theorem, the map Π : P → Y is a homeomorphism. In particular, we see that the constant curvature metric exists if and only if (1.3) holds for all proper subsets I of V.

6.2

To show the convergence of the Ricci flow for all initial choice of metrics, let us take u_{i} = ln r_{i}. Then the normalized Ricci flow becomes du_{i}/dt = −(K_{i} − K_{av}). This later equation is the negative gradient flow of a convex function f(u) defined on the u-space R^{N}. Furthermore, if we restrict to the subspace Z = {u = (u_{1}, …, u_{N}) ∈ R^{N}| ∑_{i=1}^{N} u_{i} = 0}, the function f is strictly convex Proposition 3.8. By the result in Subsection 6.1, we see that f has a critical point. Thus it is bounded from below. We claim that f satisfies the Palais-Smale condition on the plane Z. To this end, take a sequence of vectors u^{(n)} in Z so that the gradient of f at u^{(n)} tends to zero. Let r^{(n)} be the corresponding points in the space P. Then lim_{n→∞} K_{i}(r^{(n)}) = K_{av} for all indices i. By the assumption that K_{av}(1, …, 1) lies in the open cell Π(P), we see that r^{(n)} lies in a compact set in P. Thus {u^{(n)}} contains a convergent subsequence. This shows all gradient lines converge to the constant curvature metric. Thus by Proposition 3.7, the solution r(t) converges exponentially fast to the constant curvature metric.

6.3

The proof in fact shows the following for a generalization of the Ricci flow in Euclidean background metric. Namely, suppose there exists a circle packing metric R so that its curvature is C_{i} at the i-th vertex. Then the following flow dr_{i}/dt = −(K_{i} −C_{i})r_{i} has a solution for all time t ≥ 0 for all initial metrics and the solution converges exponentially fast to R.

6.4 A proof of Proposition 1.3

Proposition 1.3.

(a) If the Euler characteristic of the surface X is positive, then Condition (1.3) is valid for all generalized triangulations of X so that there are no null homotopic loops consisting of 3 edges e_{1}, …, e_{3} so that ∑_{i=1}^{k} Φ(e_{i}) ≥ π.

(b) If the Euler characteristic of the surface X is zero, then (1.3) is valid for all triangulations of X so that (1.5a) and (1.5b) hold.

This follows from Corollaries 4.2 and 4.3.

7. Some questions

There are several questions which we find interesting relating to the results in the paper.

1. Generalizing Lemma 2.2. It can be shown that Lemma 2.2 is false if the assumption Φ_{i} ∈ [0, π/2] is relaxed to Φ_{i}’s in [0, π). In fact there exists a choice of Φ_{n} ∈ [0, π) so that ∂θ_{i}/∂r_{i} < 0. But on the other hand, it seems for applications, the convexity of the function f in Proposition 3.9 is essential. Thus the question is for what choices of Φ_{n}’s in [0, π) is the matrix [s(r_{j})∂θ_{i}/∂r_{j}]_{3×3} positive or semi-positive definite.

2. 2-dimensional combinatorial Ricci flow for all piecewise constant curvature metrics. Hamilton’s Ricci flow works for all Riemannian metrics. Fix a triangulation on a surface, the analog of Riemannian metric seems to be the piecewise constant curvature metric obtained by assigning lengths to each edge in the triangulation. Is there any Ricci flow defined on the space of all these metrics? This may have some applications to the problems like, what is the space of all geometric triangulations of a triangle with the fixed combinatorial data.

3. Investigate the 2-dimensional combinatorial Ricci flow in Theorems 1.1 and 1.2 so that the combinatorial conditions (1.3) and (1.5a) and (1.5b) are not valid. The solution still exists for all time t ≥ 0. Is it true that for any solution r(t) = (r_{1}(t), …, r_{N}(t)) where t ≥ 0, the limit lim_{t→∞} r_{i}(t) always exists in the extended set [0, ∞]? In the case of the Euclidean background metric, for negative Euler characteristic closed surfaces, if r(t) with t ≥ 0 is a solution to the Ricci flow (1.3), is it true that the metric r(t) will have nonpositive curvature when t is large?

4. Investigate the 2-dimensional combinatorial Ricci flow in the case that the weight is in [0, π). For instance, can one produce a new proof of the results of Igor Rivin [12] using heat equations?

5. We showed that rigidity of the circle packing follows from the strictly convexity of the potential function in this paper (Corollary 3.11). The convexity is based on the main technical Lemma 2.3. Derive the main result of He [9] on the rigidity of locally finite infinite circle packings from the convexity of the potential function.

6. Is there any 3-dimensional combinatorial analogous of Hamilton’s 3-dimensional Ricci flow [8]?

The recent work of David Glickenstein’s UCSD thesis ([6]) seems to indicate that the analog of the Yamabe flow exists in the combinatorial setting in dimension 3 (see also [4]).

Appendix. Some computations involving triangles

A1. Basic results on triangles

Given a triangle Δv_{i}v_{j}v_{k} in one of the three geometries K^{2} = S^{2}, E^{2} and H^{2}, let the inner angle at the v_{i} vertex be θ_{i} and the length of the edge v_{j}v_{k} be x_{i}. Recall that the function s(x) is defined according to the geometry K^{2} as follows: s(x) = x for E^{2}, s(x) = sin(x) for S^{2} and s(x) = sinh(x) for H^{2}. Let A_{ijk} = s(x_{i})s(x_{j}) sin(θ_{k}). By the sine law, the quantity A_{ijk} is symmetric in i, j, k. The following is a very useful lemma for computing derivatives:

Lemma A1. In all three geometries we have:

(a) ∂θ_{i}/∂x_{i} = s(x_{i})/A_{ijk}.

(b) ∂θ_{i}/∂x_{j} = −∂θ_{i}/∂x_{i} cos(θ_{k}).

(c) ∂θ_{i}/∂x_{j}s(x_{j}) is symmetric in i, j.

(d) Consider x_{k} as a function of x_{i}, x_{j}, θ_{k}. Then

∂x_{k}/∂x_{i} = cos(θ_{j}).

The proof is a simple application of the cosine law. We will omit the details. It is interesting to note that these derivatives formulas are the same for all three geometries.

One interesting consequence of Lemma A1(c) is the following:

Corollary A2. For any triangle in the geometry K^{2}, the 1-form ∑_{l∈{i,j,k}} θ_{l}s(x_{l})dx_{l} in variables x_{i}, x_{j}, x_{k} is closed.

A2. A proof of Lemma 2.3

A simpler proof using mathematical software Maple VII is given in the next subsection. In this subsection, we present a conventional proof.

Suppose we have a collection of three closed disks C_{i}, C_{j}, and C_{k} centered at v_{i}, v_{j} and v_{k} so that their radii are r_{i}, r_{j} and r_{k} and their exterior intersection angles are ϕ_{i}, ϕ_{j}, ϕ_{k} ∈ [0, π) in geometry K^{2}. Consider the triangle formed by v_{i}, v_{j}, v_{k}. Let its inner angle at v_{n} be θ_{n} and the edge length opposite to v_{n} be x_{n}. We want to show that ∂θ_{i}/∂r_{j}s(r_{j}) is symmetric in i, j.

First of all if L_{i}, L_{j} and L_{k} are the geodesic lines passing through the pairs of the intersection points of {C_{k}, C_{j}}, {C_{k}, C_{i}} and {C_{i}, C_{j}} (L_{i} is the tangent to C_{j} and C_{k} if they intersect in one point), then the three lines L_{i}, L_{j}, L_{k} intersect in one point.

To see this, we note that the result is well-known in the Euclidean geometry E^{2}. To see the result in hyperbolic geometry, let O be the point of intersection of L_{i} and L_{j}. Take the disk model for H^{2} so that O is the Euclidean center. Then both L_{i} and L_{j} are Euclidean line segments. Let L′_{k} be the Euclidean diameter passing through O and one of the intersection point of C_{i} with C_{j}. The by the result in the Euclidean case, we see that L_{k} must contain the other point of intersection of C_{i} and C_{j}. This shows, L′_{k} = L_{k}. The same argument also works for the spherical case where we consider the stereographic projection from the antipodal point of O. Let u_{r} be an intersection point of the circles C_{s} and C_{t} where {r, s, t} = {i, j, k}.

To begin the proof, by Lemma A1, we have

s(r_{j})∂θ_{i}/∂r_{j} = s(r_{j})(∂θ_{i}/∂x_{i}∂x_{i}/∂r_{j} + ∂θ_{i}/∂x_{k}∂x_{k}/∂r_{j})

= s(r_{j})∂θ_{i}/∂x_{i}(∂x_{i}/∂r_{j} − cos(θ_{j})∂x_{k}/∂r_{j})

= \frac{s(x_{i}) sin(θ_{j})}{A_{ijk}} \frac{s(r_{j})(cos(θ_{j}^{ki′}) − cos(θ_{j}) cos(θ_{j}^{ik′}))}{sin(θ_{j})}.

Here θ_{j}^{ik′} and θ_{j}^{ki′} are the inner angles at v_{j} in the triangles Δv_{j}v_{i}u_{k} and Δv_{j}v_{k}u_{i}. Note that the first fraction s(x_{i}) sin(θ_{j})/A_{ijk} is symmetric in i, j due to the sine law. Thus it suffices to show that

\frac{s(r_{j})(cos(θ_{j}^{ki′}) − cos(θ_{j}) cos(θ_{j}^{ik′}))}{sin(θ_{j})}

is symmetric in i, j.

To this end, we will need the following lemma about quadrilaterals in K^{2} so that two opposite angles are right angles.

Lemma A3. Suppose Q is an immersed quadrilateral in geometry K^{2} so that its four edges are T, X, Y, Z counted clockwise. Suppose the inner angle between sides {T, X} and {Y, Z} are right angles and the inner angle between sides {X, Y } is θ, and edges T, Y are disjoint. Let the lengths of sides X, Y, Z be x, y, z and t be the length of T if X ∩ Z = ∅ and t be the negative of the length of T if X intersects Z. Then the following hold:

(a) In the Euclidean geometry E^{2},

t = (y − x cos θ)/ sin θ.

(b) In the hyperbolic geometry H^{2},

tanh(t) = cosh(x)(tanh(y) − tanh(x) cos(θ))/ sin(θ).

(c) In the spherical geometry S^{2},

tan(t) = cos(x)(tan(y) − tan(x) cos(θ))/ sin(θ).

The proof is a direct application of trigonometries for right angled triangles and quadrilaterals with three right angles. (See for instance [15].)

Another simple fact we shall use is the following formulas for right angled triangles. Suppose a right angled triangle has three edge lengths a, b, c and whose opposite angles are α, β and π/2. Then we have, cos(α) = b/c in E^{2}, cos(α) = tanh(b)/ tanh(c) in H^{2}, and cos(α) = tan(b)/ tan(c) in S^{2}.

Let the distance from the common intersection O to the intersection point of the lines L_{k} and v_{i}v_{j} be d. Let D be d if O is inside the triangle and −d otherwise. It is symmetric in i, j. Then by the above lemma and the trigonometric formulas, we obtain that the expression s(r_{j})(cos(θ_{j}^{ki′})−cos(θ_{j}) cos(θ_{j}^{ik′}))/ sin(θ_{j}) is equal to the D, tanh(D) and tan(D) respectively. This verifies the symmetry. Note that if all angles Φ_{i}’s are in [0, π/2], then the common intersection point O is inside the triangle. Thus d > 0 which is what Lemma 2.2(b) states.

A3. A proof of Lemma 2.3 using Maple VII

The simplest proof of the lemma is to use some mathematical software so that we do not have to go over all possible configurations. We will present such a proof using Maple VII below.

Let T_{3} be the space of all possible configurations of pairwise intersecting three circles in K^{2} up to isometry so that their centers form a triangle. The we claim that T_{3} is connected. To see this, since the space of all triangles up to isometry is connected, it suffices to show that the subspace of all pairwise intersecting three circles with fixed centers is connected. To see the later space, let us exam the three radii. We can choose the radius of the first circle arbitrary as long as it lies in its natural interval (e.g, it is (0, ∞) for E^{2} and H^{2}, and is (0, π/2) for S^{2}). Now the radius of the second circle must also be in an interval since it intersects the first circle. The radius of the third must be in an interval as well since it intersects the first and the second circle and these two circles intersect. This shows that the space is connected.

Now to show ∂θ_{i}/∂r_{j}s(r_{j}) is symmetric in i, j, it is much convenient for the machine to verify that (∂θ_{i}/∂r_{j}s(r_{j}))^{2} is symmetric in i, j. On the other hand, both functions ∂θ_{i}/∂r_{j}s(r_{j}) and ∂θ_{j}/∂r_{i}s(r_{i}) are analytic in variables Φ_{i}, Φ_{j}, Φ_{k}, r_{i}, r_{j}, r_{k} and defined on a connected space so that they coincide in the subspace r_{i} = r_{j}. Thus ∂θ_{i}/∂r_{j}s(r_{j}) must be symmetric in i, j if its square is symmetric.

To verify the symmetry of ((∂θ_{i}/∂r_{j})r_{j})^{2} in i, j for Euclidean geometry E^{2} using Maple VII, we run the following:

> yi := sqrt (rj^{2} + rk^{2} + 2 ∗ rj ∗ rk ∗ bi); > yj := sqrt (ri^{2} + rk^{2} + 2 ∗ ri ∗ rk ∗ bj); > yk := sqrt(rj^{2} + ri^{2} + 2 ∗ rj ∗ ri ∗ bk); > ai := arccos(((yj)^{2} + (yk)^{2} − (yi)^{2})/(2 ∗ (yj) ∗ (yk))); > fij := diff (ai, rj) ∗ rj; > g1 := simplify (fij); > g2 := g1^{2}; > g3 := subs ({ri = rj, rj = ri, bi = bj, bj = bi}, g2) − g2; > simplify (g3); 0

To verify the symmetry of ((∂θ_{i}/∂r_{j}) sinh(r_{j}))^{2} in i, j for hyperbolic geometry H^{2} using Maple VII, we run the following:

> yi := arccosh (cosh(rj) ∗ cosh(rk) + sinh(rj) ∗ sinh(rk) ∗ bi); > yj := arccosh (cosh(rk) ∗ cosh(ri) + sinh(ri) ∗ sinh(rk) ∗ bj); > yk := arccosh (cosh(rj) ∗ cosh(ri) + sinh(rj) ∗ sinh(ri) ∗ bk); > ai := arccos((cosh(yj)∗cosh(yk)−cosh(yi))/(sinh(yj)∗sinh(yk))); > fij := diff (ai, rj) ∗ sinh(rj); > g1 := simplify (fij); > g2 := g1^{2}; > g3 := subs ({ri = rj, rj = ri, bi = bj, bj = bi}, g2) − g2; > simplify (g3); 0

To verify the symmetry of ((∂θ_{i}/∂r_{j})r_{j})^{2} in i, j for spherical geometry S^{2} using Maple VII, we run the following:

> yi := arccos(cos(rj) ∗ cos(rk) + sin(rj) ∗ sin(rk) ∗ bi); > yj := arccos(cos(rk) ∗ cos(ri) + sin(ri) ∗ sin(rk) ∗ bj); > yk := arccos(cos(rj) ∗ cos(ri) + sin(rj) ∗ sin(ri) ∗ bk); > ai := arccos((− cos(yj) ∗ cos(yk) + cos(yi))/(sin(yj) ∗ sin(yk))); > fij := diff (ai, rj) ∗ sin(rj); > g1 := simplify (fij); > g2 := g1^{2}; > g3 := subs ({ri = rj, rj = ri, bi = bj, bj = bi}, g2) − g2; > simplify (g3); 0

This ends the proof.

References

[1] A. Bobenko & B. Springborn, Variational principles for circle patterns and Koebe’s theorem, preprint, math.GT/0203250.

[2] L.-T. Cheng, private communications.

[3] B. Chow, The Ricci flow on the 2-sphere, J. Differential Geom. 33(2) (1991) 325–334, MR 92d:53036, Zbl 0734.53033.

[4] D. Cooper & I. Rivin, Combinatorial scalar curvature and rigidity of ball packings, Math. Res. Lett. 3(1) (1996) 51–60, MR 97k:52022, Zbl 0868.51023.

[5] Y.C. de Verdière, Un principe variationnel pour les empilements de cercles, Invent. Math. 104(3) (1991) 655–669, MR 92h:57020, Zbl 0745.52010.

[6] D. Glickenstein, A maximum principle for combinatorial Yamabe flow, preprint, math.MG/0211195.

[7] R.S. Hamilton, The Ricci flow on surfaces, Mathematics and general relativity (Santa Cruz, CA, 1986), 237–262, Contemp. Math., 71, Amer. Math. Soc., Providence, RI, 1988, MR 89i:53029, Zbl 0663.53031.

[8] R.S. Hamilton, Three-manifolds with positive Ricci curvature, J. Differential Geom. 17 (1982) 255–306, MR 84a:53050, Zbl 0504.53034.

[9] Z.-X. He, Rigidity of infinite disk patterns, Ann. of Math. (2) 149(1) (1999) 1–33, MR 2000j:30068, Zbl 0922.30020.

[10] A. Marden & B. Rodin, On Thurston’s formulation and proof of Andreev’s theorem, Computational methods and function theory (Valparaiso, 1989), 103–115, Lect. Notes in Math., 1435, Springer, Berlin, 1990, MR 92b:52040, Zbl 0717.52014.

[11] B. Mohar, Circle packings of maps in polynomial time, European J. Combin. 18(7) (1997) 785–805, MR 99f:52022, Zbl 0891.52008.

[12] I. Rivin, A characterization of ideal polyhedra in hyperbolic 3-space, Ann. of Math. (2) 143 (1996) 51–70, MR 96i:52008, Zbl 0874.52006.

[13] K. Stephenson, Circle packing software, http://www.math.utk.edu/˜ kens/.

[14] W. Thurston, Geometry and topology of 3-manifolds, Princeton lecture notes, 1976, http://www.msri.org/publications/books/gt3m/.

[15] E.B. Vinberg, Geometry. II, Encyclopaedia of Mathematical Sciences, 29, Springer-Verlag, New York, 1988, MR 94f:53002, Zbl 0786.00008.

Dept. of Math.

UCSD, La Jolla, CA 92093

Dept. of Math.

Rutgers Univ., New Brunswick, NJ 08854