title: Combinatorics encoding geometry: the legacy of Bill Thurston in the story of one theorem
authors: Philip L. Bowers
text: 
  
  
  
  Language Models as Emotional Classifiers 
   for Textual Conversation
      David M. Schwartz
      December 30, 2023
  ===================================================================
  
  
  
  
  
  
  This article presents a whirlwind tour of some results surrounding the Koebe-Andre'ev-Thurston Theorem, Bill Thurston's seminal circle packing theorem that appears in Chapter 13 of The Geometry and Topology of Three-Manifolds. 
  
  
  
  
  
  
  § INTRODUCTION
   
  Bill Thurston was the most original and influential topologist of the last half-century. His impact on the discipline of geometric topology during that time is unsurpassed, and his insights in the topology and geometry of three-manifolds led finally to the resolution of the most celebrated problem of topology over the last century—The Poincaré Conjecture. He made fundamental contributions to many sub-disciplines within geometric topology, from the theory of foliations on manifolds to the combinatorial structure of rational maps on the two-sphere, and from geometric and automatic group theory to classical polyhedral geometry. Of course his foundational work on three-manifolds, first laid out in his courses at Princeton in the late nineteen-seventies, compiled initially as a Princeton paper-back monograph inscribed by Bill Floyd and available upon request as The Geometry and Topology of Three-Manifolds (GTTM) <cit.>, and maturing as the famous Thurston Geometrization Conjecture of the early nineteen-eighties, was the driving force behind the development of geometric topology for the next thirty years. The final confirmation of the Geometrization Conjecture by Giorgi Perelman using the flow of Ricci curvature, following a program that had been introduced by Richard Hamilton, is one of the crown jewels of twentieth century mathematics.
  
  Thurston marks a watershed in the short history of topology,[I will use the term topology henceforth to mean geometric topology. By dropping the adjective geometric I certainly mean no slight of general, set-theoretic, or algebraic topology.] a signpost, demarcating topology before Thurston, and topology after Thurston. This is evidenced not only in the fabulous results he proved, explained, and inspired, but even more so in how he taught us to do mathematics. Topology before Thurston was dominated by the general and the abstract, entrapped in the rarified heights that captured the mathematical world in general, and topology in particular, in the period from the 1930's until the 1970's. Topology after Thurston is dominated by the particular and the geometric, a throwback to the nineteenth-century, having much in common with the highly geometric landscape that inspired Felix Klein and Max Dehn, who walked around and within Riemann surfaces, knew them intimately, and understood them in their particularity. Thurston's vision gave a generation of topologists permission to get their collective hands dirty by examining in great depth specific structures on specific examples.
  
  One of the organizing principles that lies behind Thurston's vision is that geometry informs topology, and that the non-Euclidean geometry of Lobachevski, Bolyai, and Beltrami in particular is systemic to the study of topology. Hyperbolic geometryhyperbolic geometry permeates topology after Thurston, and it is hyperbolic geometry that becomes the common thread of the present article. This will be seen in the interrelated studies presented here. All to varying degrees are due to the direct influence of Bill Thurston and his generalization of the earlier results of Koebe and Andre'ev. All involve hyperbolic geometry in some form or influence, and even further all illustrate how combinatorics encodes geometry, another of the principles that underlies Thurston's vision. To my mind, the proposition that combinatorics encodes geometry, which in turn informs topology has become a fundamental guiding motif for topology after Thurston. I offer this article as a celebration of Bill Thurston's vision and his immense influence over our discipline.
  
  
  
   §.§ An introductory overview.
   The Koebe-Andre'ev-Thurston Theorem represents a rediscovery and broad generalization of a curiosity of Paul Koebe's from 1936, and has an interpretation that recovers a characterization of certain three-dimensional hyperbolic polyhedra due to E.M. Andre'ev in two papers from 1970. This theorem is the foundation stone of the discipline that has been dubbed as discrete conformal geometry,discrete conformal geometry which itself has been developed extensively by many mathematicians in many different directions over the last thirty years. Discrete conformal geometry in its purest form is geometry born of combinatorics, but it has theoretical and practical applications. In the theoretical realm, it produces a discrete analytic function theory that is faithful to its continuous cousin, a quantum theory of complex analysis from which the classical theory emerges in the limit of large scales. In the realm of applications, it has been developed in a variety of directions, for practical applications in areas as diverse as biomedical imaging and 3D print head guidance. This rather large body of work flows from simple insights that Thurston presented in his lecture at Purdue University in 1985 on how to use the most elementary case of his circle packing theorem to provide a practical algorithm for approximating the Riemann mapping from a proper, simply-connected planar domain to the unit disk. A personal accounting of this development can be found in the author's own review <cit.> of the bible of circle packing theory, Ken Stephenson's Introduction to Circle Packing: The Theory of Discrete Analytic Functions <cit.>. 
  
  A perusal of the Table of Contents at the beginning of the article will give the reader a clue as to where I am going in this survey. I primarily stick with the theoretical results for which there are fairly direct lines from the Koebe-Andre'ev-Thurston Theorem to those results. This means in particular that I almost totally ignore the really vast array of practical applications that circle packing has found, especially in the last two decades as discrete differential geometry has become of primary importance in so many applications among computer scientists and computational geometers. A survey of applications will have to wait as space constraints preclude a discussion that does justice to the topic.
  
  
  
  
   §.§ Dedication and Appreciation.
   This article is dedicated to the memory of Bill Thurston and his student Oded Schramm, and to an appreciation of Jim Cannon and Ken Stephenson. I have spoken already of Bill Thurston's legacy. Oded Schramm was one of the first to press Thurston's ideas on circle packings to a high level of development and application, and his great originality in approaching these problems has bequeathed to us a treasure trove of beautiful gems of mathematics. Most of Oded's work on circle packing and discrete geometry was accomplished in the decade of the nineteen-nineties. As Bill is a demarcation point in the history of topology, Oded is one in the history of probability theory. In the late nineties, Oded became interested in some classical open problems in probability theory generated by physicists, in percolation theory and in random planar triangulations in particular. Physicists had much theoretical and computational evidence for the veracity of their conjectures, but little mathematical proof, or even mathematical tools to approach their verifications. In Oded's hands these venerable conjectures and problems began to yield to mathematical proof, using ingenious tools developed or refined by Oded and his collaborators, chief among which are SLE_κ, originally Stochastic-Loewner Evolution, now renamed as Schramm-Loewner Evolution, and UIPT's, or Uniform Infinite Planar Triangulations. For a wonderful biographical commentary on Oded's contributions to mathematics, see Steffen Rohde's article Oded Schramm: From Circle Packing to SLE in <cit.>.
  
  
  The two individuals who have had the greatest impact on my mathematical work are Jim Cannon and Ken Stephenson, the one a mathematical hero of mine, the other my stalwart collaborator for three decades. Jim's work has influenced mine significantly, and I greatly admire his mathematical tastes and contributions. Pre-Thurston, Jim had made a name for himself in geometric topology in the flavor of Bing and Milnor, having solved the famous double suspension problem and having made seminal contributions to cell-like decomposition theory and the characterization of manifolds. In the beginning of the Thurston era, his influential paper The combinatorial structure of cocompact discrete hyperbolic groups <cit.> anticipated many of the later developments of geometric group theory, presaging Gromov's thin triangle condition and, à la Dehn, the importance of negative curvature in solving the classical word and conjugacy problems of combinatorial group theory. He with Thurston invented automatic group theory and then Jim settled upon the conjecture that bears his name as the work that for three decades has consumed his attention. Ken has been a joy with whom to collaborate over the past three decades. He was inspired upon attending Thurston's Purdue lecture in 1985 to change his mathematical attentions from a successful career as a complex function theorist, to a geometer exploring this new idea of circle packing using both traditional mathematical proof and the power of computations for mathematical experimentation. I began my foray into Thurston-style geometry and topology by answering in <cit.> a question of Ken and Alan Beardon from one of the first research papers <cit.> to appear on circle packings after Rodin and Sullivan's 1987 paper <cit.> confirming the conjecture of Thurston from the Purdue lecture. Ken and I are co-authors on a number of research articles and his down-to-earth approach to the understanding of mathematics has been a constant check on my tendency toward flights of fancy. I have learned from him how to tell a good story of a mathematical topic. For Ken's warm friendship and collaboration I am grateful.
  
  
  
   §.§ Acknowledgements.
   I thank Prof. Athanase Papadopoulos for inviting me to write on a favorite theme of mine to honor Bill Thurston and his legacy. It has been a pleasure for me to review the impact derived from this one beautiful little gem of Thurston. I thank Ken Stephenson for permission to use the graphics of Figures 1, 2, 5, and 7, and John Bowers for generating the graphics for Figures 3, 4, 6, 8, 9, and 10. 
  
  
  
  § THE KOEBE-ANDRE'EV-THURSTON THEOREM, PART I
   
  
  
  
  
   §.§ Koebe uniformization and circle packing.
   In the early years of the twentieth century, rigorous proofs of the Riemann Mapping Theorem and the more general Uniformization Theorem were given by such eminent mathematicians as Osgood, Carathéodory, Poincaré, and Koebe, and refinements and re-workings would continue to be made by others, even up to the present.[The author recommends rather highly the article On the history of the Riemann mapping theorem <cit.> by Jeremy Gray and the monograph Uniformization of Riemann Surfaces: Revisiting a Hundred-Year-Old Theorem <cit.>. These two works give insightful historical accountings of the discovery, articulation, understanding, and finally rigorous proofs of the Riemann Mapping Theorem and the Uniformization Theorem. The narratives are at once engaging and perceptive, illustrating wonderfully the fact that mathematics is generally a common endeavor of a community of folks rather than the singular achievement of an enlightened few.] The generalization of the Riemann Mapping Theorem to multiply-connected domains fell to the hands of Paul Koebe, who in 1920 in <cit.> proved that every finitely-connected domain in the Riemann sphere is conformally equivalent to a circle domain, a connected open set all of whose complementary components are points or closed round disks. Of course for a 1-connected, or simply-connected, domain this is nothing more than the Riemann Mapping Theorem. He proved also a rigidity result, that any conformal homeomorphism between any two circle domains with finitely many complementary components is in fact the restriction of a Möbius transformation.[Beware! This is not true in general. Two domains with uncountably many complementary components may be conformally equivalent yet fail to be Möbius equivalent.] Koebe's real goal was what is known by its German name as Koebe's Kreisnormierungsproblem and by its English equivalent as Koebe's Uniformization Conjecture,Koebe uniformization conjecture which he posed in 1908.
  
  [<cit.>]
      Every domain in the Riemann sphere is conformally homeomorphic to a circle domain.
  
  
  This of course includes those domains with infinitely many, whether countably or uncountably many, complementary components. The general Koebe Uniformization Conjecture remains open to this day. More on this later.
  
  In a paper of 1936, Koebe obtained the following circle packing theorem as a limiting case of his uniformization theorem of 1920. This went unnoticed by the circle packing community until sometime in the early nineteen-nineties. 
  
  [<cit.>]
  Every oriented simplicial triangulation K of the 2-sphere 𝕊^2 determines a univalent circle packing K(𝒞) for K, unique up to Möbius transformations of the sphere.
  
  Here the circle packingcircle packing K(𝒞) is a collection 𝒞 = {C_v: v∈ V(K)} of circles C_v in the sphere 𝕊^2 indexed by the vertex set V(K) of K such that C_u and C_v are tangent whenever uv is an edge of K, and for which circles C_u, C_v, and C_w bound a positively oriented interstice whenever uvw is a positively oriented face of K. The circle packing is univalent if there is a collection 𝒟 = {D_v : v∈ V(K)} of disks with C_v = ∂ D_v whose interiors are pairwise disjoint.[Without univalence, packings with branching would be allowed, where the sequence of circles tangent to a single circle C may wrap around C multiple times before closing up. See Section <ref>.] Connecting the centers of the adjacent circles by appropriate great circular arcs then produces a geodesic triangulation of 𝕊^2 isomorphic to K. <Ref> shows a  circle packing of the sphere determined by an abstract triangulation K, and the realization of K as a geodesic triangulation. Of course the circle packings for a fixed K are Möbius equivalent, while the corresponding geodesic triangulations are not, simply because neither circle centers nor great circles are Möbius-invariant. I will look at a proof of the Koebe Circle Packing Theorem later, but first I'll present Thurston's generalization.
  
  
  
  
  
  
   §.§ Koebe-Andre'ev-Thurston, or KAT for short.
  Koebe-Andre'ev-Thurston Theorem In his Princeton course of 1978-79, Thurston greatly generalized the Koebe Circle Packing Theorem, though at the time he was unaware of Koebe's result. He generalized in two ways, first by allowing adjacent circles to overlap and second by extending the theorem to arbitrary compact orientable surfaces. Thurston realized that his version of the theorem on the sphere 𝕊^2 in fact encodes information about convex hyperbolic polyhedra, the connection of course through the fact that the sphere 𝕊^2 serves as the space at infinity of the Beltrami-Klein and Poincaré ball versions of hyperbolic three-space ℍ^3 with circles on the sphere the ideal boundaries of hyperbolic planes in ℍ^3. These polyhedra had been characterized in two papers of Andre'ev from 1970, whose results can be interpreted in terms of the existence and uniqueness of the circle packings Thurston examined in his generalization of Koebe. Thurston's generalization to overlapping packings on the sphere is now known as the Koebe-Andre'ev-Thurston Theorem, honoring its three principle protagonists.
  
  
  Let K be an oriented simplicial triangulation of 𝕊^2, different from the tetrahedral triangulation, and let Φ : E(K) → [0, π/2] be a map assigning angle values to each edge of K. Assume that the following two conditions hold.
  
  
    (i) If e_1, e_2, e_3 form a closed loop of edges from K with ∑_i=1^3Φ(e_i) ≥π, then e_1, e_2,  and e_3 form the boundary of a face of K.
  
    (ii) If e_1, e_2, e_3, e_4 form a closed loop of edges from K with ∑_i=1^4Φ(e_i) = 2π, then e_1, e_2, e_3, and e_4 form the boundary of the union of two adjacent faces of K.
  
  Then there is a realization of K as a geodesic triangulation of 𝕊^2 and a family 𝒞 = { C_v : v ∈ V(K)} of circles centered at the vertices of the triangulation so that the two circles C_v and C_w meet at angle Φ(e) whenever e=vw is an edge of K. The circle packing 𝒞 is unique up to Möbius transformations.
  
  
  
  
  Now I want to point out that exactly what is called the Koebe-Andre'ev-Thurston Theorem is not at all settled. Some references use the term to mean the tangency case of the theorem (Φ≡ 0), which is nothing more than the Koebe Circle Packing Theorem, while others use the term to mean Thurston's full generalization of the theorem to arbitrary closed surfaces that is presented in Section <ref>. Exactly what Thurston proved in GTTM also often is misreported. In fact my introduction to this section is a bit of a misreporting, so let me take a little time to say exactly what Thurston does in Chapter 13 of GTTM. 
  
  In terms of circle packings on the 2-sphere, Thurston does not allow overlaps of adjacent circles, only tangencies. His version of the tangency case appears as Corollary 13.6.2 in Chapter 13 of GTTM, and appears as a corollary of Theorem 13.6.1, which he attributes to Andre'ev. This theorem concerns hyperbolic structures on orbifolds and, as it was Thurston who invented the notion of orbifold in his course at Princeton during 1976-77 as recorded in the footnote on page 13.5 of Chapter 13 of GTTM itself, this theorem is an interpretation of Andre'ev's in the context of orbifolds. Thurston does not give a proof of Theorem 13.6.1, but uses its result ensuring the existence of a hyperbolic structure on a suitable orbifold to prove Koebe's Theorem of 1936, Corollary 13.6.2. He does this by using the triangulation K to define an associated polyhedron P by cutting off vertices by planes that pass through midpoints of edges. He then uses the Andre'ev result to realize P as a right-angled ideal polyhedron in ℍ^3. The faces of this polyhedron then lie in planes whose ideal circular boundaries are the circles of the desired tangency packing complemented by the orthogonal circles through three mutually adjacent points of tangency. He then invokes Mostow rigidity for uniqueness. 
  
  It isn't until he presents Theorem 13.7.1 that Thurston allows for adjacent circles to overlap with angle between zero and π/2, and that only for surfaces other than the sphere, those surfaces with nonpositive Euler characteristic. Thurston proves this by assigning polyhedral metrics with curvature concentrated at the vertices v_1, … ,v_n by assigning a radius r_i at vertex v_i. Defining the mapping c:ℝ^n→ℝ^n that measures the curvature via c(r)_i = 2π - (the angle sum at vertex v_i), he then argues in nine pages that the origin 0 is in the image of c, which implies the desired result. It is the case that the version Thurston presents on the sphere, Corollary 13.6.2, is Koebe's result, and uses Andre'ev's ideas for the proof. It is only with this positive genus version, Theorem 13.7.1, that Thurston puts forth new geometric ideas, fertile enough to spawn an industry dedicated to understanding polyhedral metrics on surfaces and their induced circle packings.
  
  Thurston's approach to circle packing is rather entwined with his overall concern, that of hyperbolic structures on three-dimensional manifolds and orbifolds. Since this work of the nineteen-seventies, Thurston's circle packing results have spawned a rather extensive theory that is more combinatorial and geometric, and related more to classical complex function theory and Riemann surfaces, and less to three-manifolds. It is related intimately to hyperbolic polyhedra and their generalizations, this the subject of Section <ref>, and has found several scientific applications. In the hands of folks like Ken Stephenson and his students and collaborators, it has spawned a discrete theory of complex analytic functions, laid out ever so elegantly in Stephenson's Introduction to Circle Packing <cit.>. It has yielded beautiful results on, for example, discrete minimal surfaces in the hands of the Berlin school of Bobenko, Hoffman, Springborn, Pinkall, and Polthier; see for example <cit.> and  <cit.>. Though the theory now is rather mature, it continues to interact in new and interesting ways with new areas, for instance lying in the background in conformal tilings <cit.>, or in the foreground with its interaction with the classical rigidity theory of Euclidean frameworks <cit.>. There is an immense literature here, and so much of it owes a great debt of gratitude to the insights of Bill Thurston.
  
  
  
  
   §.§ A proof of the Koebe Circle Packing Theorem.
  
  Rather than proving the whole of KAT I, I will address the case where Φ is identically zero and prove Koebe's result. The proof presented here can be modified to give a complete proof of KAT I, which is done in <cit.> in proving a generalization.[See Section <ref>.] Koebe's original proof of his namesake theorem uses a limiting process on circle domains and classical analytic arguments on convergence of analytic families of maps, very much in the flavor of what we now teach as classical techniques in our complex analysis courses. There are now many proofs of the Koebe Circle Packing Theorem. To name a few, besides Koebe's, there is Thurston's in GTTM already outlined above based on Andre'ev's results on hyperbolic polyhedra, Al Marden and Burt Rodin's using piecewise flat polyhedral metrics, Alan Beardon and Ken Stephenson's <cit.> that adapts the classical Perron method for constructing harmonic maps as an upper envelope of subharmonic maps, Colin de Verdière's <cit.> based on a variational principle, Igor Rivins's hidden in his paper <cit.> on Euclidean structures on triangulated surfaces, the author's <cit.> that turns the Beardon-Stephenson proof upside down to address packings on punctured surfaces, and Alexandre Bobenko and Boris Springborn's <cit.> that uses a minimal principle on integrable systems. Here I present a geometric and combinatorial proof where hyperbolic geometry is the crucial ingredient. The proof is a twist on the Perron method used by Beardon and Stephenson in <cit.> and is specialized from a more general version that applies to arbitrary surfaces of finite conformal type that appears in <cit.>. We will see that it has the advantage of generalizing in interesting ways.
  
  
  By removing one vertex v_0 from K and its adjacent edges and faces, one obtains a triangulation T of a closed disk. Place a piecewise hyperbolic metric on T as follows. For any positive function r:V(T) → (0, ∞), let |T(r)| be the metric space obtained by identifying the face v_1v_2v_3 of T with the hyperbolic triangle of side lengths r(v_i) + r(v_j) for i≠ j ∈{1,2,3}. This places a piecewise hyperbolic metric on T with cone-like singularities at the interior vertices. This structure often now is called a piecewise hyperbolic polyhedral metric, and the function r is called variously a radius vector or label. For any vertex v, one can measure the angle sum θ_r(v) of the angles at v in all the faces incident to v. I will say that r is a superpacking label for T if the angle sums of all interior vertices are at most 2π, and a packing label[For emphasis one sometimes calls this a hyperbolic packing label to distinguish it from flat or Euclidean packing labels that also find their use in this discipline.] if all are equal to 2π.
  
  Now modify this a little by allowing r to take infinite values at the boundary vertices. This causes some ambiguity only if there is a separating edge in T that disconnects T when removed. This will be taken care of later, so for now assume no separating edge exists. The goal is to find a packing label 𝔯 with 𝔯(w) = ∞ whenever w is a boundary vertex. Assuming that such an 𝔯 exists, we may glue on hyperbolic half planes along the faces with two boundary vertices to give a complete hyperbolic metric on a topological disk, which must be isometric to the hyperbolic plane. This implies that the metric space |T(𝔯)| is isometric to an ideal polygon in the hyperbolic plane whose sides are hyperbolic lines connecting adjacent ideal vertices that correspond to the boundary vertices of T. Now placing hyperbolic circles of radii 𝔯(v) centered at interior vertices v and horocycles centered at ideal vertices determined by the boundary vertices gives a univalent circle packing of the hyperbolic plane realized as, say, the Poincaré disk, the unit disk 𝔻 in the complex plane with Poincaré metric ds = 2 |dz| / (1-|z|^2). The boundary circles are horocycles in the hyperbolic metric on the disk and are therefore circles internally tangent to the unit circle. Stereographic projection to the sphere 𝕊^2 and addition of the equator as the circle corresponding to the vertex v_0 removed initially produces a univalent circle packing of the sphere in the pattern of K as desired. Uniqueness follows from uniqueness of the packing label 𝔯 with infinite boundary values, which follows from the construction of 𝔯 explained next.
  
  Define the function 𝔯 as
  
      𝔯(v) = inf {r(v) : r∈ℜ}
  
  where
  
      ℜ = {r: V(T) → (0, ∞]: r  is a superpacking label for T with infinite boundary values}.
  
  The claim is that this is the desired packing label. The first observation is that ℜ≠∅ so that we are not taking the infimum of the empty set. This is because one may choose label values so large on the interior vertices that all of the faces become hyperbolic triangles whose interior angles are no more than 2π / d, where d is the maximum degree of all the vertices of T. It follows that 𝔯 is a non-negative function with infinite boundary values. To verify that 𝔯 is a packing label, I show that
  
  
    (i) 𝔯 cannot take a zero value on any interior vertex, which then implies that 𝔯∈ℜ,
  
     and,
  
    (ii) the angle sum at any interior vertex is 2π, meaning further that 𝔯 is a packing label.
  
  We need two preliminary observations.
  
  
    (iii) Hyperbolic area is bounded away from zero. The hyperbolic area of the singular hyperbolic surface |T(r)| is ≥π for all superpacking labels r∈ℜ.
  
    (iv) Monotonicity of angles. For a face f=v_0v_1v_2 of T, let α_r(i), for i=0,1,2, be the angle that the label r∈ℜ gives to f at vertex v_i. Then α_r(0) ↑π, α_r(1)↓ 0, and α_r(2) ↓ 0 monotonically as r(v_0) ↓ 0 when r(v_1) and r(v_2) are held fixed.
  
  
  In calculating the hyperbolic area to confirm item (iii), let V(T) and F(T) be the respective vertex and face sets of T of respective cardinalities 𝚅 and 𝙵. The sum of the angles of a face when given its metric by r is denoted α_r (f) so that its hyperbolic area is A_r(f) = π - α_r(f). Finally, with 𝚅_int and 𝚅_bd denoting the numbers of interior and boundary vertices of T so that 𝚅 = 𝚅_int + 𝚅_bd, one has
  
      hyp-area(|T(r)|) = π 𝙵 - ∑_f∈ F(T)α_r(f) 
          = π 𝙵 - ∑_v∈ V(T)θ_r(v) ≥π (𝙵 -2𝚅_int),
  
  since θ_r(v) ≤ 2π at interior vertices and θ_r(v) = 0 at boundary ones. An Euler characteristic exercise then shows that 𝙵 -2𝚅_int = 𝚅_bd - 2 ≥ 1, the inequality holding since K is simplicial. It follows that every superpacking label with infinite boundary values produces a metric on T with hyperbolic area at least π. Item (iv) is almost obvious from drawing examples, but can be given a rigorous proof using the hyperbolic law of cosines from hyperbolic trigonometry.
  
  I now address item (i). First the claim is that the label 𝔯 cannot be identically zero on the set of interior vertices. Indeed, if 𝔯 is identically zero, one may choose a sequence of superpacking labels r_i with infinite boundary values such that, for each interior vertex v, r_i(v) → 0 as i →∞. This latter fact in turn follows from the observation that the minimum label min{r_1, r_2} is in ℜ whenever r_1 and r_2 are labels in ℜ, which in turn is a consequence of the monotonicity of angles (iv). Recall that we are under the assumption that there are no separating edges so that at least one vertex of any face f of T is interior. Any such interior vertex has r_i-values converging to zero, and any boundary one is fixed at infinity, and with this it is easy to see that the hyperbolic area A_r_i(f) → 0 as i →∞. But this implies that the hyperbolic area of |T(r_i)| converges to zero as i→∞, which contradicts item (iii). 
  
  Now could it be that 𝔯 takes a zero value at some interior vertex, but not at all? The argument that this in fact does not happen is a generalization of what I have argued thus far. I will but give an indication of how it goes, referring the reader to <cit.> for details. Let T' be the subcomplex of T determined by those faces of T that have a vertex in 𝔯^-1(0). An argument using Euler characteristic similar to that already given implies that the hyperbolic area of |T'(r)| is positive and bounded away from zero for every superpacking label r with fixed non-negative boundary values. But an argument as in the preceding paragraph shows that the hyperbolic areas of |T'(r_i)| converge to zero for a sequence of superpacking labels with fixed boundary values and interior vertex values converging to zero. This contradiction implies that 𝔯 is a positive function on the interior vertex set, and continuity of angles of a triangle with respect to edge lengths implies that θ_𝔯(v) = lim_i→∞θ_r_i(v) ≤ 2π at any interior vertex, since θ_r_i(v) ≤ 2 π for all i. This shows that 𝔯∈ℜ and completes the verification of item (i).
  
  Item (ii) follows quickly from item (iv). Indeed, if (ii) fails, then there is an interior vertex v of T such that θ_𝔯(v) < 2π. By the monotonicity properties (iv), varying 𝔯 by slightly decreasing its value at v without changing any other values increases θ_𝔯(v) while decreasing θ_𝔯(w) for any vertex w incident to v. By making that decrease of 𝔯(v) small enough to keep the angle sum at v below 2π, we obtain a superpacking label r with infinite boundary values that satisfies r(v) < 𝔯(v), which contradicts the definition of 𝔯 in Equation <ref>.
  
  At this point I have shown that 𝔯 is a packing label with infinite boundary values, and I now claim that it is the only one. Suppose there is a packing label r in ℜ that differs from the infimum label 𝔯 defined in Equation <ref>. Then 𝔯 (v) ≤ r(v) for all vertices v, but there must be some interior vertex w with 𝔯(w) < r(w). This implies that the hyperbolic area of the surface |T(𝔯)| is strictly less than that of |T(r)|. But this is impossible since 𝔯 and r are packing labels with infinite boundary values, and as argued above, both |T(𝔯)| and |T(r)| are ideal hyperbolic polygons with 𝚅_Bd sides. An easy exercise shows that the hyperbolic area of any such hyperbolic polygon is equal to (𝚅_Bd -2)π. 
  
  This completes the proof modulo the assumption that T has no separating edge. This is handled by induction on the number of such edges. If there is one separating edge uv, cut T into T_1 and T_2 along that edge, circle pack each in the unit disk with horocyclic boundary circles, and then using Möbius transformations, place the T_1 packing in the upper half disk with the horocycles for u and v circles tangent at the origin and centered on the real axis, and place the T_2 packing in the lower half of the disk with those same horocylic circles for u and v. This is possible since T is oriented, and this gives an appropriate packing label of T with infinite boundary values.
  
  
  
  
  
   §.§ Maximal packings and the boundary value problem.
   This proof actually proves the following extremely useful fact, which Beardon and Stephenson <cit.> exploited to give the first extension of the Koebe Circle Packing Theorem to infinite packings of the disk and the plane. The infinite theory is presented in Section <ref>.
  
  
  Every oriented simplicial triangulation T of a closed disk determines a univalent circle packing T(𝒞) for T in the unit disk 𝔻 in the complex plane ℂ, unique up to Möbius transformations of the disk, with the circles corresponding to boundary vertices of T internally tangent to the unit circle boundary ∂𝔻 = 𝕊^1. Moreover, when given its canonical hyperbolic metric making 𝔻 into the Poincaré disk model of the hyperbolic plane ℍ^2, the circle radii of the packing are uniquely determined by T.  
  
  
  The circle packing guaranteed by this theorem is called the maximal packing for T. This theorem is in fact a special case of the more general result of Beardon and Stephenson <cit.> that solves the discrete version of the classical Dirichlet boundary value problem of harmonic analysis. In that paper, the authors also prove a discrete version of the classical Schwarz-Pick Lemma of complex analysis. These two theorems finish up the present section.
  
  [Beardon and Stephenson <cit.>]
  Let T be an oriented simplicial triangulation of a closed disk and f:V_Bd(T) → (0,∞] a function assigning positive or infinite values to the boundary vertices. Then there exists a unique hyperbolic packing label 𝔯: V(T) → (0,∞] extending f. The resulting circle packing T(𝒞_𝔯) of the unit disk 𝔻 is unique up to Möbius transformations of 𝔻.
  
  
  
  The proof is a straightforward modification of that of the Koebe Circle Packing Theorem already presented. Again 𝔯 = infℜ is the desired packing label, provided that
  
      ℜ = {r: r  is a superpacking label for T with r(w) ≥ f(w)  when  w∈ V_Bd(T) }.
  
  Of course, f ≡∞ gives the maximal packing of the preceding theorem.
  
  This proof is a modification of the Beardon-Stephenson proof, which uses subpacking rather than superpacking labels. In a subpacking label, the interior angle sums are greater than or equal to 2π and one obtains the packing label as an upper envelope of subpacking labels, with the packing label given by 𝔯 = supℜ' where ℜ' is the set of subpacking labels with boundary values given by f. The advantage of approaching the desired packing label 𝔯 from above using superpackings (infℜ) rather than from below using subpackings (supℜ') is that this upper Perron method readily generalizes to include cusp type singularities and cone type singularities at interior vertices.[Another not insignificant advantage is that it is easy to show that ℜ≠∅ while proving that ℜ' ≠∅ generally is difficult.] This is presented in Section <ref>.
  
  A word of warning here. When the boundary values are allowed to be finite, the resulting packing, though locally univalent, may not be globally univalent. This means that the disks bounded by the circles of the packing may overlap non-trivially, though ones neighboring the same interior vertex never do; this is the meaning of locally univalent. <Ref> shows a locally univalent packing that is not globally univalent.
  
  
  The second theorem of Beardon and Stephenson follows partly from the proof of the first (item (i)), and the rest of the theorem follows from a careful analysis of paths and angles in piecewise hyperbolic surfaces. The details of course appear in <cit.>. The theorem I state here is the generalization of what the reference <cit.> calls the Discrete Schwarz-Pick Lemma, which in turn is obtained by setting the boundary values of r identically to infinity.
  [Beardon and Stephenson <cit.>]
  Let r, r' ; V(T) → (0,∞] be packing labels for the oriented simplicial triangulation T of a closed disk. Suppose that r(w) ≥ r'(w) at every boundary vertex w∈ V_Bd(T). Then
  
      
    (i) r ≥ r'; i.e., r(v) ≥ r'(v) at every vertex v of T;
      
    (ii) ρ_r(u,v) ≥ρ_r' (u,v) for any two vertices u and v, where ρ_r is the distance function on the metric surface |T(r)|, and similarly for ρ_r';
      
    (iii) A_r(f) ≥ A_r'(f) for any face f of T. (Recall that A_r(f) is the hyperbolic area of the face f.)
  
  Moreover, if a single instance of finite equality occurs at an interior vertex in (i), or at vertices u and v at least one of which is interior in (ii), or at any face in (iii), then r=r'.
  
  
  
  
  § THE KOEBE-ANDRE'EV-THURSTON THEOREM, PART II
  Koebe-Andre'ev-Thurston Theorem
  
  
   §.§ Circle packings of compact surfaces.
   
  Thurston's other avenue of generalization of Koebe, indeed the more far-reaching one, is his extension of KAT to arbitrary orientable closed surfaces. Here there are striking illustrations of how purely combinatorial information encodes precise geometry. I will start with Thurston's tangency case of packings before presenting his version with overlaps.
  
  
  Let K be an oriented simplicial triangulation of a closed surface S_g of positive genus. Then there is a metric of constant curvature, unique up to scaling, on S_g that supports a univalent, tangency circle packing 𝒞 = { C_v: v∈ V(K)} modeled on K. In particular, C_u and C_v are tangent whenever uv is an edge of K. The packing 𝒞 is unique up to isometries of S_g in this metric when g≥ 2, and up to scaling when g=1. Connecting the centers of adjacent circles by geodesic shortest paths produces a geodesic triangulation of the surface in the pattern of K. The metric is locally Euclidean when g=1 and locally hyperbolic otherwise.
  
  
  Just in case the reader blinked and missed it, I aim to emphasize the extent to which combinatorics determines geometry in this theorem. The simplicial complex K provides purely combinatorial data with topological overtones. Yet hidden inside of the combinatorics is precise geometry. For example in the hyperbolic case where g > 1, among the uncountably many possible pairwise distinct hyperbolic metrics of constant curvature -1 as tabulated in the (6g-6)-dimensional moduli space ℳ(S_g) ≅ℝ^6g-6, the complex K chooses exactly one of these metrics, and in that metric, determines a univalent circle packing unique up to isometry! For none of the other metrics that S_g supports is there a univalent tangency packing of circles in the pattern of K! Since there are only countably many pairwise distinct simplicial triangulations of the fixed surface S_g, only countably many of the metrics parameterized by ℳ(S_g) support any univalent tangency packing at all, though the set of metrics that do support such circle packings does form a dense subset of the moduli space. 
  
  I present a proof of Theorem <ref> based on the upper Perron method used to prove the Koebe Circle Packing Theorem.
  
  	Let ℜ = { r: V(K) → (0, ∞): θ_r (v) ≤ 2π for all  v∈ V(K)}, the set of superpacking labels for K. Here again, exactly as in the proof of the Koebe Circle Packing Theorem, the label r determines a hyperbolic polyhedral metric surface |K(r)|. A unique packing label for which the angle sum at every vertex is equal to 2π would give all the claims of the theorem in the hyperbolic case. My claim is that when g ≥ 2, the function 𝔯 = infℜ is the unique packing label for K, and when g=1, then 𝔯 = infℜ is identically zero, but provides a way to place a flat polyhedral metric on K that meets the packing condition. 
  	
  Exactly the calculation of Inequality <ref> gives hyp-area(|K(r)|) ≥ (𝙵 - 2 𝚅) π for any superpacking label r ∈ℜ, and an Euler characteristic argument gives
  	
      𝙵 - 2 𝚅 = - 2 χ(S_g) = 4g-4.
  
  When g≥ 2 so that 𝙵 - 2 𝚅 is positive and hence hyp-area(|K(r)|) is positive, the same argument used in the proof of the Koebe Circle Packing Theorem shows that items (i) and (ii) of that proof hold, so that 𝔯 is a packing label. Uniqueness follows exactly as in that proof. 
  
  
  The remaining case is when g=1 so that S_g is a topological torus. Here are the steps in proving that S_1 supports a flat metric that supports a univalent circle packing in the pattern of K, both the packing and the metric unique up to scaling.
  
      
    (i) When g=1, 𝙵 - 2𝚅 = 0 and this implies that 𝔯 = infℜ is identically zero on V(K).
      
    (ii) Fix a vertex v^† in K and let ℜ^† = { r^†: r∈ℜ}, where r^† is the normalized label defined by r^†(v) = r(v) / r(v^†).
      
    (iii) Show that 𝔯^† = infℜ^† takes only positive values.
      
    (iv) Let |K(𝔯^†)|_flat be the flat polyhedral surface with cone type singularities obtained by identifying a face v_1v_2v_3 with the Euclidean triangle of side-lengths 𝔯^†(v_i) + 𝔯^†(v_j) for i≠ j ∈{1,2,3}. 
      
    (v)Show that  |K(𝔯^†)|_flat is non-singular; i.e.,  𝔯^† is a flat packing label with Euclidean angle sums θ_𝔯^†^flat(v) = 2π at every vertex v.
      
    (vi) Show that 𝔯^† is the unique flat packing label with value 1 at v^†.
  
  The details of the argument appear in <cit.>, but I will give an indication of why this outline works to prove the desired result. Let A(r) be the hyperbolic area of the singular hyperbolic surface |K(r)| when r ∈ℜ and observe that 
  
      A(r) - s(r) = (𝙵 - 2 𝚅) π,   where   s(r) = ∑_v∈ V(K) (2π - θ_r(v)).
  
  Here s(r) is the total angle shortage.[Also called the discrete curvature.] In the genus 1 case, - 2 𝚅 =0 so A(r) = s(r) for all superpacking labels r∈ℜ. Now assuming that item (i) has been verified, any superpacking label r that is close to the infimum infℜ = 0 has area A(r) close to zero and hence so too is the shortage s(r) close to zero. In the limit as r→infℜ =0, the shortages s(r) → 0 and this implies that the singular hyperbolic surfaces |K(r)| have angle sums θ_r (v) → 2π for every vertex v. Since Euclidean geometry is the small scale limit of hyperbolic geometry, this implies that the Euclidean angle sums θ_r^flat(v) → 2π as r → 0. Thus the collection {|K(r)|_flat}_r ∈ℜ is a collection of singular flat surfaces whose singularities are removed in the limit as r→ 0. Of course there is no limiting surface since r → 0. Whereas this cannot be remedied in hyperbolic geometry, it can be remedied in Euclidean geometry by rescaling the labels r as described in item (ii). With item (iii) confirmed so that the flat polyhedral surface |K(𝔯^†)|_flat of item (iv) exists, since similarity transformations exist in Euclidean geometry, these rescalings preserve the Euclidean angles and imply that the limit surface |K(𝔯^†)|_flat is non-singular.  Items (v) and (vi) just state formally the result of making this imprecise but rather accurate discussion rigorous.
  
  
  
  
  
  
  
  
  
  
   §.§ KAT for compact surfaces
   Thurston's Theorem 13.7.1 of GTTM combines the introduction of surfaces of genus greater than zero in Theorem <ref> with the overlap conditions of the KAT Circle Packing Theorem.
  
  [Theorem 13.7.1, GTTM]
  	Let K be an oriented simplicial triangulation of a surface S_g of genus g≥ 1, and let Φ : E(K) → [0, π/2] be a map assigning angle values to each edge of K. Assume that the following two conditions hold.
  
  
    (i) If e_1, e_2, e_3 form a closed loop of edges from K with ∑_i=1^3Φ(e_i) ≥π, then e_1, e_2,  and e_3 form the boundary of a face of K.
  
    (ii) If e_1, e_2, e_3, e_4 form a closed loop of edges from K with ∑_i=1^4Φ(e_i) = 2π, then e_1, e_2, e_3, and e_4 form the boundary of the union of two adjacent faces of K.
  
  Then there is a metric of constant curvature on S_g, unique up to scaling, and a realization of K as a geodesic triangulation in that metric, as well as a family 𝒞 = { C_v : v ∈ V(K)} of circles centered at the vertices of the triangulation so that the two circles C_v and C_w meet at angle Φ(e) whenever e=vw is an edge of K. The circle packing 𝒞 is unique up to isometry.
   
  
  I already have discussed the proof in GTTM. Let me say further that it was in this proof that Thurston introduced the idea of using labels, or radii assignments to vertices, to build a polyhedral surface with cone type singularities, and then to vary the labels until the packing condition is met. This is still the basic idea for proving many packing results, though the way in which one varies the labels and the choice of initial labels changes from researcher to researcher and from application to application. The Perron method used in this article is a modification of the method of Beardon and Stephenson <cit.>. This idea also led to a practical algorithm for producing the packing labels that was the starting point for Ken Stephenson's . This sophisticated software package for computing circle packings has enjoyed extensive development over the past thirty years and is freely available at Ken's webpage.  
  
  Before I introduce infinite circle packings and their really interesting and novel features in Section <ref>, I'll discuss two generalizations of the KAT Theorems. The first is presented in Section <ref> and generalizes KAT I to certain branched packings of the 2-sphere where circles tangent to a given one wrap around that one more than once. These packings of course fail to be univalent, but provide a rich family of packings that model the behavior of polynomial mappings of the Riemann sphere. The ultimate goal is to model arbitrary rational mappings of the sphere, which would require the theory to extend to more general branch structures, this a topic of current research; see for example <cit.>. The second is presented in Section <ref> and examines how to include both cusps with ideal vertices as well as prescribed discrete curvature at pre-chosen vertices.
  
  
  
   §.§ A branched KAT theorem and polynomial branching
  circle packing!branched Ken Stephenson and I generalized KAT I by allowing for polynomial branching to occur in the circle packing. Branching means that we allow for the angle sums at predetermined vertices to be a positive integer multiple of 2π rather than just 2π, or stated differently, we allow the circles tangent to a given one to wrap around that given circle multiple times before closing up; see <Ref>.
  
  Polynomial means that half the branching is concentrated at one vertex. The terminology comes from the classical theory of rational maps. Indeed, rational mappings may be thought of as branched self-mappings of the 2-sphere, and the polynomial mappings are precisely those in which there is an even amount of branching with half the branching occurring at a single point. Taken together, a circle packing promised by the next theorem mimics the behavior of a polynomial mapping of the Riemann sphere. 
  
  Our proof of the theorem as presented in <cit.> offers an independent proof of KAT I, which the branched version reduces to when the branch structure β is empty. In fact as far as I know, it was the first full direct proof of KAT I given that Thurston proves only the tangency case (the Koebe Circle Packing Theorem) and Marden-Rodin <cit.>, though allowing overlapping circles, has more restrictive hypotheses. KAT I is implied by Igor Rivin's earlier work, which bears the same resemblance to KAT I as does Andre'ev's in that it is a result on the existence of hyperbolic polyhedra. 
  
  I state the result and then backtrack to fill in definitions and discuss the proof.
  
  [Bowers and Stephenson <cit.>]
  Let K be an oriented simplicial triangulation of 𝕊^2, different from the tetrahedral triangulation, and let Φ : E(K) → [0, π/2] be a map assigning angle values to each edge of K. Assume that the following two conditions hold.
  
  
    (i) If e_1, e_2, e_3 form a closed loop of edges from K with ∑_i=1^3Φ(e_i) ≥π, then e_1, e_2,  and e_3 form the boundary of a face of K.
  
    (ii) If e_1, e_2, e_3, e_4 form a closed loop of edges from K with ∑_i=1^4Φ(e_i) = 2π, then e_1, e_2, e_3, and e_4 form the boundary of the union of two adjacent faces of K.
  
  If β is a polynomial branch structure for the edge-labeled triangulation (K, Φ), then there exists a circle packing 𝒞 = { C_v : v ∈ V(K)} for (K, Φ), a family of circles in 𝕊^2 so that the two circles C_v and C_w meet at angle Φ(e) whenever e=vw is an edge of K, with br(𝒞) = β. The circle packing 𝒞 is unique up to Möbius transformations.
  
  
  A branch structure essentially is a listing of some of the vertices of K, each paired with an integer ≥ 2 that indicates how many times the circles adjacent to the ones corresponding to the selected vertices wrap around before closing up. Before making this precise, let's observe that there must be further combinatorial conditions to ensure that a branched circle packing exists for the branch structure. Indeed, note that when there is no branching, the fact that K is a simplicial triangulation implies that the degree of each vertex is at least three, and this local condition guarantees that there are enough circles adjacent to a given circle to wrap around once, with angle sum 2π, at least in the tangency case. A moment's thought will show that if the desire is that there be branching of multiplicity m≥ 2 at a circle C_v, meaning that the circles adjacent to C_v wrap around m times before closing up, there had better be at least 1+ 2m adjacent ones to achieve the angle sum of 2π m. This may not be sufficient but certainly is necessary, and the definition of a polynomial branch structure includes enough combinatorial conditions to ensure sufficiency.
  
  To clothe this discussion in a bit of flesh, suppose that 𝒞 = {C_v: v ∈ V(K)} is a circle packing for the pair (K, Φ). For each vertex v∈ V(K), identify v with the center of its corresponding circle C_v. Fixing a vertex v, let v_1, …, v_n be the list of neighbors of v forming the consecutive vertices in a walk around the boundary of the star st(v) of v, and let α_i be the measure of the spherical angle ∠ v_ivv_i+1. Then v is said to be a branch point of order 𝔬 = m-1, or of multiplicity m, if θ(v) = 2π m for some integer m≥ 2, where θ(v) = α_1 + ⋯ + α_n is the angle sum at v; again, see <Ref>. The branch set br(𝒞) of the circle packing is the set of ordered pairs (v,𝔬(v)) as v ranges over the branch points and 𝔬(v) is the order of v. It is clear that the combinatorics of K as well as the values of Φ restrict the branch orders. 
  
  My aim is to construct circle packings of 𝕊^2 in the pattern of K with overlaps given by Φ with a given, predetermined branch set. Toward this end, I will define a branch structure on the complex T = K ∖Int[st(v_∞)] that triangulates the closed disk one obtains by deleting one vertex, v_∞, and its incident open cells from K. I will use Φ_T to mean the restriction of Φ to the vertices of T.
  [branch structure]
  A set β = {(v_1, 𝔬_1,), … ,(v_ℓ, 𝔬_ℓ)}, where v_i, …, v_ℓ is a pairwise distinct list of interior vertices of T and each 𝔬_i is a positive integer, is a branch structure for the pair (T, Φ_T) if the following condition holds: for each simple closed edge path γ = e_1⋯ e_n in T that bounds a combinatorial disk D that contains at least one of the vertices v_i, the inequality
  
      ∑_i=1^n[ π - Φ_T(e_i)] > 2π  (𝔬(D) +1)
  
  holds, where 𝔬(D) = ∑𝔬_i, the sum taken over all indices i for which v_i∈Int (D).
  
  We will see that this condition on the combinatorics of T and the values of Φ_T ensures that there are no local obstructions to the existence of a circle packing for (T, Φ_T) whose branch set is β, and in fact is enough to ensure that there are no global ones. 
  [polynomial branch structure]
  Let K be a simplicial triangulation of 𝕊^2 with edge function Φ : V(K) → [0,π/2]. A collection
  
      β = {(v_∞,𝔬_∞), (v_1, 𝔬_1), … (v_ℓ, 𝔬_ℓ)}
  
  is a polynomial branch structure for (K, Φ) if the following conditions prevail.
  
      
    * 𝔬_∞ = 𝔬_1 + ⋯ + 𝔬_ℓ.
      
    * The vertices v_1, …, v_ℓ are all interior vertices of the complex T = K ∖Int[st(v_∞)].
      
    * β_T = { (v_1, 𝔬_1), … (v_ℓ, 𝔬_ℓ)} is a branch structure for (T,Φ_T).
      
    * No Φ-edge labeled subgraph of the type given in <Ref> occurs in K where v is one of the branch vertices v_1, … ,v_ℓ.
  
  
  
  A few comments concerning this definition are in order. Item (1) says that there is an even amount of branching and half of it occurs at vertex v_∞; item (2) says that no branch vertex from the list v_1, …, v_ℓ is adjacent to the vertex v_∞; item (3) in particular says that Inequality <ref> holds for (T, Φ_T); item (4) is a technical condition that avoids impossible configurations.
  
  
  How do we put all of this together to prove the Polynomially Branched KAT Theorem? Letting β = {(v_∞,𝔬_∞), (v_1, 𝔬_1), … (v_ℓ, 𝔬_ℓ)} be a polynomial branch structure for (K, Φ), we remove the vertex v_∞ and work with hyperbolic polyhedral metrics on the disk triangulation T as in the proof of the Koebe Circle Packing Theorem. The idea is the same as there in that we want to use vertex labels on T to describe hyperbolic triangles that then are identified with faces to form a singular hyperbolic surface, and then vary the labels to meet angle targets at the vertices. There are three new difficulties that appear. 
  
      
    (i) Target overlap angles are given by Φ_T for adjacent circles rather than tangencies. 
      
    (ii) Rather that 2π, the target angle sums at branch vertices are 2π m_i for integers m_i = 𝔬_i + 1 ≥ 2. 
      
    (iii) As the boundary ∂𝔻 ultimately will serve as the circle corresponding to v_∞ in the desired circle packing, the overlaps of the boundary circles of the packing for T must intersect the unit circle at the angles demanded by Φ.
  
  Now items (i) and (ii) are really no problem as superpacking labels can be described that allow for prescribed overlap angles for adjacent circles and target angles prescribed by the branch structure. The real difficulty is item (iii). If we use radius labels, the best we can do is, as in the proof of the Koebe Theorem, get boundary circles that meet the unit circle at single points with intersection angle zero. The hint for resolving this difficulty is found in thinking a bit more about the role of circles in hyperbolic geometry, and in particular in the Poincaré disk model where ℍ^2 is identified with the unit disk 𝔻, and the ideal boundary of ℍ^2 is identified with ∂𝔻 = 𝕊^1. Euclidean circles that meet the Poincaré disk 𝔻 not only serve as hyperbolic circles, but also as horocycles and hypercycles. Those that lie entirely within 𝔻 are hyperbolic circles, those internally tangent to the ideal boundary 𝕊^1 are horocycles, and those that meet the boundary in two points a and b are hypercycles whose points in 𝔻 lie equidistant to the hyperbolic line with ideal endpoints a and b. This latter case includes the hyperbolic geodesic lines. What proves fruitful here is the fact that, when oriented, these Euclidean circles and circular arcs are precisely the curves of constant geodetic curvature in the hyperbolic plane. This is implied immediately by the fact that these are the flow lines of 1-parameter groups of hyperbolic isometries, the hyperbolic circles the flow lines of elliptic flows, horocycles of parabolic flows, and hypercycles of hyperbolic flows. 
  
  
  Here are the salient facts about the geodetic curvature κ of an arc of an oriented Euclidean circle that lies in the Poincaré disk 𝔻. Call an arc c= C∩𝔻, where C is a Euclidean circle that meets 𝔻, a cycle with parent circle C. There is a normalized setting in which the curvature can be read off easily. Apply a conformal automorphism of the disk so that c passes through the origin and its parent circle C is centered on the positive real axis. Orient c counterclockwise and let t, 0 < t ≤∞ denote the point of intersection of C with the interval (0, ∞]. Then the curvature satisfies κ = κ (c) = 1/t. In terms of intrinsic parameters, for counterclockwise-oriented hypercycles when t > 1, κ(c) = cosα where α is the acute angle of intersection of C with the unit circle. This includes the case of a hyperbolic geodesic where α = π/2 and κ = 0. Assuming still the counterclockwise orientation, when t=1, c is a horocycle with κ(c) = 1, and when t<1, c = C is a hyperbolic circle of some hyperbolic radius r with κ(c) =  r.
  
  For our purposes it is quite fortuitous that monotone curvature parameters for cycles can be used as vertex labels on T in place of radii labels to encode a singular hyperbolic metric on a disk that T triangulates. The curvature is inversely related to the radii, but the really important feature is that, unlike radii labels, the curvature label can be used to identify faces of T, not only with hyperbolic triangles with both finite and ideal vertices, but also triangles with “hyperideal vertices.”[When the Klein disk is used as the model for the hyperbolic plane  these are in fact Euclidean triangles that meet the disk, but whose vertices may lie within the disk, on the ideal boundary, or outside the closed disk. The hyperideal vertices are the latter ones.] This means that when curvatures κ_1, κ_2, and κ_3 label the vertices of the face f and values Φ_T(e_i) for i=1,2,3 label the opposite edges, the face f may be identified with the region of the hyperbolic plane determined by cycles of curvatures κ_1, κ_2, and κ_3 overlapping with angles Φ_T(e_i) for i=1,2,3. This accomplishes two things. First, the overlaps of cycles are given by the edge function Φ_T. Second, and very importantly, if the vertex w of f is a boundary vertex and the value κ = cosΦ_T (w v_∞) is used for the curvature, then the boundary cycle corresponding to w overlaps with the unit circle by an angle of Φ_T (w v_∞). 
  
  The important point is that the set 𝔎 of curvature labels, ones whose boundary values are given by g(w) = cosΦ(wv_∞) for the boundary vertex w, and that produce superpackings where the angle sums at interior vertices are no more than 2π at non-branch points and no more than 2π m_i at branch point v_i, may be varied to obtain a β-packing label, this time as sup𝔎, the supremum instead of the infimum since curvatures are inversely related to radii. Of course by β-packing label I mean that the angle sum at any interior vertex that is not a branch vertex is 2π, and at v_i is 2π m_i. The argument is akin to that of the proof of the Koebe Circle Packing Theorem, but, though still elementary, is much more intricate and involved. The full detailed proof appears in  <cit.> where the key proposition, stated below, generalizes the Discrete Boundary Value Theorem of Beardon and Stephenson. Setting up this result with appropriate definitions and analysis of hyperideal hyperbolic triangles, as well as the proof itself, takes up most of the content of the paper.
  
  [Bowers and Stephenson <cit.>]
  	Let g be a proper boundary label for T and β a branch structure for (T, Φ_T). Then there exists a unique β-packing label 𝔨 for (T, Φ_T) such that 𝔨 (w) = g(w) for every boundary vertex of T.
  
  
  This then is used to complete the proof of the Polynomially Branched KAT Theorem by using the circle packing produced by Proposition <ref>, augmented by the unit circle corresponding to the removed vertex v_∞ to define 𝒞. Much of this becomes routine at this point, except that one still must confirm that half the branching occurs at v_∞. This turns out to be nontrivial. Again the details are rather involved and can be found in <cit.>.
  
  
  
  
  
  
   §.§ Cusps and cone type singularities.
   In this section I offer a generalization of KAT II where prescribed target angle sums at vertices are assigned, and  necessary and sufficient conditions are sought to guarantee existence of such packings. This is the discrete version of the classical Schwarz-Picard problem of the existence of hyperbolic metrics on Riemann surfaces with prescribed cone type singularities. For simplicity I am going to restrict to the tangency case where Φ is identically zero. 
  
  To set up the problem, let K be a simplicial triangulation of a compact surface, possibly with boundary, with 𝙵 faces, 𝙴 edges, and 𝚅 vertices. The vertex set V(K) is partitioned into three sets: two disjoint subsets of interior vertices denoted as V_Int and V_cusps, and the set V_Bd of boundary vertices, with respective cardinalities 𝚅_Int, 𝚅_cusps, and 𝚅_Bd. Elements of V_Int are called interior vertices and of V_cusps are called cusp vertices. Two functions are given, the first f: V_Bd→ (0, ∞] giving target radii for the boundary vertices and the second θ: V_Int→ (0, ∞) giving target angle sums at interior vertices. The target angle sums at the cusp vertices in V_cusps are zero. The task is to give necessary and sufficient conditions on K to guarantee the existence of a packing label r: V(K) → (0, ∞] for this data such that r = f on V_Bd, r = ∞ on V_cusps, and θ_r (v) = θ (v) for every interior vertex v ∈ V_Int.
  
  To describe a solution to this problem, for any set V of vertices, let 𝙵_V denote the number of faces of K that meet V, and let θ(V) = ∑_v∈ Vθ (v) denote the total angle sum of the vertices of V. Let
  
      ℜ = { r: V(K) → (0, ∞] : r=f  on   V_Bd,    r= ∞ on  V_cusps,  θ_r(v) ≤θ(v)  for all  v∈ V_int}.
  
  This describes the set of superpacking labels for the data θ with boundary values given by f and cusp set V_cusps. A packing label for this data is a superpacking label where, in addition, the target angle sums given by θ are met, so that θ_r(v) = θ(v) for all v∈ V_Int. For any superpacking label r and vertex set V, let θ_r (V) = ∑_v∈ Vθ_r(v). The next theorem gives necessary and sufficient conditions for a solution to the discrete Schwarz-Picard boundary value problem. The proof is a generalization of the proof presented herein for the Koebe Circle Packing Theorem. There the important invariant is 𝙵 - 2 𝚅_Int. In the borderless case of Theorem <ref>, the important invariant is 𝙵 - 2 𝚅. These arise from writing the hyperbolic area of the surface determined by a packing label, provided one exits, in terms of combinatorial invariants. The corresponding fact in this setting is that, for any packing label 𝔯 for the data f, θ, and V_cusps, 
  
      hyp-area(K(𝔯)) + θ_𝔯(V_Bd) = π 𝙵 - θ_𝔯 ( V_Int) = π 𝙵 - θ (V_Int).
    
  The right hand side of this equation is an invariant of K and θ and must be positive since the left hand side is positive. Also, for every interior vertex v, 
  
      θ(v) = θ_𝔯(v) < π deg  v
  
  These give two necessary conditions for a desired label to exist, but these are not sufficient. Nonetheless, these two conditions are the extreme cases of the sufficient condition that appears as item (i) of the theorem. 
  
  [Bowers <cit.>]
   The following are equivalent.
   
   
    (i) For every edge-path connected set V ⊂ V_Int of interior vertices, the invariant π 𝙵_V - θ(V) is positive.
   
    (ii) The function 𝔯 = infℜ does not take a zero value at any vertex.
   
    (iii) The function 𝔯 = infℜ is the unique packing label for K with data f, θ, and V_cusps.
   
    (iv) There exist a packing label for K for the data f, θ, and V_cusps.
   
  
  
  A word of caution is in order. Though this does solve the discrete Schwarz-Picard problem, the combinatorial condition of item (i), that π 𝙵_V - θ(V) > 0 for every path connected subset V of interior vertices, is a very difficult condition to check once the size of K becomes in any way substantial. This pure mathematician has learnt to appreciate the difficulties our computational geometer cousins face when trying to make the elegant output of our theorems practical tools for performing geometric computations. This difficulty often is unrecognized or left unacknowledged by my pure mathematician siblings.
  
  
  
  
  
  
  
  § INFINITE PACKINGS OF NON-COMPACT SURFACES.
  circle packing!infinite I now turn our attention to infinite packings of non-compact surfaces. Here new and interesting phenomena arise, fraught with their own peculiar difficulties. To keep the conversation manageable, I am restricting attention to tangency circle packings of simply connected domains and will concentrate on one very interesting problem that arises in this setting—the type problem—and one great success in attacking the Koebe Uniformization Conjecture.
  
  
  
  
  
  
  
  
   §.§ The Discrete Uniformization Theorem.
   Does every simplicial triangulation K of every topological surface S, compact or not, admit a circle packing in some geometric structure on S? By passing to the universal covering surface S and lifting the triangulation to a triangulation K of S, the question may be approached by asking whether any G-invariant simplicial triangulation of a simply connected surface admits a G-invariant circle packing in some geometric structure, where G is a group of symmetries of the complex. There are only two simply connected surfaces up to homeomorphism, the sphere and the plane. The former case is addressed by the Koebe Circle Packing Theorem. In this section I will address the latter case.
  
  Let 𝒯 be a plane triangulation graph, by which I mean that 𝒯 is the 1-skeleton of a simplicial triangulation K of the topological plane. There are precisely two inequivalent conformal structures on the plane, the one conformally equivalent to the complex plane ℂ and the other to the open unit disk 𝔻. There are precisely two complete metrics of constant curvature up to scaling on the plane, the one isometric to Euclidean 2-space 𝔼^2 and of constant zero curvature, the other isometric to the hyperbolic plane ℍ^2 and of constant negative curvature. Fortunately, the conformal and the geometric structures mesh nicely in that the complex plane ℂ is a conformal model of plane Euclidean geometry via its standard Euclidean metric ds_ℂ= |dz|, and the disk 𝔻 is a conformal model of plane hyperbolic geometry via the Poincaré metric ds_𝔻 = 2|dz|/(1-|z|^2). Metric circles in these two geometries are precisely the Euclidean circles contained in their point sets, so circle packings in these geometric surfaces can be identified with Euclidean circle packings of ℂ and 𝔻.  I will use 𝔾[𝔾 means 𝔾eometry.] to mean either ℂ or 𝔻 with the intrinsic Euclidean or hyperbolic geometry determined by either ds_ℂ or ds_𝔻 when referring to geometric quantities like geodesics and angles, etc. Here is the foundational result in this setting. 
  
  [Beardon and Stephenson <cit.>, He and Schramm <cit.>]
  	Every plane triangulation graph 𝒯 can be realized as the contacts graph of a univalent circle packing 𝒯(𝒞) that fills exactly one of the complex plane ℂ or the disk 𝔻. The packing is unique up to conformal automorphisms of either ℂ or 𝔻. 
  
  
  The contacts graph of a collection is a graph with a vertex for each element of the collection and an edge between two vertices if an only if the corresponding elements meet. The carrier of the circle packing 𝒞 in the geometry 𝔾 is the union of the geodesic triangles formed by connecting centers of triples of mutually adjacent circles with geodesic segments, and 𝒞 fills 𝔾 whenever its carrier is all of 𝔾. When 𝒞 is univalent and fills 𝔾, 𝒞 is said to be a maximal packing for 𝒯 or K, and K may be realized as a geodesic triangulation of 𝔾 whose vertices are the centers of the circles of 𝒞 with geodesic edges connecting adjacent centers.
  
  Once this theorem is in place, the whole of the theory of tangency circle packings on non-compact surfaces comes into play. As already indicated, in a thoroughly classical way packing questions on surfaces can be transferred to questions of packings on simply connected surfaces, this by passing to covering spaces acted upon by groups of deck transformations. Any combinatorial symmetries of the complex K are realized as automorphic symmetries of 𝔾, this from the uniqueness of the Discrete Uniformization Theorem, and this offers an alternate proof of Theorem <ref>, and an extension of that theorem to triangulations of arbitrary, non-compact surfaces.
  
  Beardon and Stephenson <cit.> proved the Discrete Uniformization Theorem when 𝒯 has bounded degree, a global bound on the degrees of all the vertices of 𝒯. In this foundational paper as well as in their subsequent one <cit.>, Beardon and Stephenson laid out a beautiful theory of circle packings on arbitrary surfaces, gave a blueprint for developing a theory of discrete analytic functions, and articulated one of the most interesting problems in the discipline, that of the circle packing type problem for non-compact surfaces, this latter the subject of the section following. The bounded degree assumption was needed both to verify that the packing fills 𝔾 and for the uniqueness, and He and Schramm <cit.> removed the bounded degree hypothesis and proved the general case where there is no global bound on the degrees of vertices. Earlier, Schramm <cit.> had proved a very general rigidity theorem for infinite packings of planar domains whose complementary domains are a countable collection of points, and He and Schramm <cit.> extended this to general countably connected domains. 
  
  The full proof is scattered throughout several articles published in the nineteen-nineties. In what constitutes a significant service to the discipline, Ken Stephenson has laid out a complete proof in roughly fifty pages of his wonderful text Introduction to Circle Packing <cit.>. I have not the space here to do justice to the argument, but I will make some comments.
  
  Beardon and Stephenson's proof of existence relies on the Maximal Disk Packing Theorem and uses a diagonal argument on a sequence of finite subcomplexes of K that exhausts K. It does not depend on any bounded degree assumption and is quite straightforward. The proof of existence goes like this. Write K = ∪_i=1^∞ K_i as a nested, increasing union of finite subcomplexes K_i, each a simplicial triangulation of a closed disk. Apply the Maximal Disk Packing Theorem to obtain a sequence 𝒞_i of univalent, maximal circle packings for the complexes K_i in the unit disk 𝔻 realized as the Poincaré disk model of hyperbolic geometry. Fix a base vertex v_0 of K_1 and let C_i be the circle of 𝒞_i that corresponds to v_0. By applying an automorphism of the disk if needed, assume that C_i is centered at the origin and of hyperbolic radius 𝔯_i(v_0). Now the Discrete Schwarz-Pick Lemma implies that the sequence 𝔯_i(v_0) of hyperbolic radii is non-increasing, hence has a limit, say 𝔯(v_0) ≥ 0, as i→∞. There are two cases.
  	
  	
    (I) The limit radius 𝔯(v_0) ≠ 0;
  	
    (II) The limit radius 𝔯(v_0) = 0.
  	
  The first claim is that if v is any other vertex of K whose corresponding circle of 𝒞_i, for large enough i, has hyperbolic radius 𝔯_i(v), then lim_i→∞𝔯_i(v) is not zero when case (I) occurs and is equal to zero when case (II) occurs. This means that the limit radius function 𝔯: V(K) → [0, ∞) never takes a zero value in case (I) and is identically zero in case (II). The proof of this claim uses the Ring Lemma of Burt Rodin and Dennis Sullivan that was crucial in <cit.> in their confirmation of Thurston's outlined proof of the Discrete Riemann Mapping Theorem presented in his 1985 Purdue lecture; see Section <ref>. The Ring Lemma guarantees the existence of a sequence of positive constants 𝔠_d such that, when d≥ 3 disks form a cycle of sequentially tangent disks all tangent to a central disk of Euclidean radius R, and the disks have pairwise disjoint interiors, then the smallest disk has Euclidean radius ≥𝔠_dR. The Ring Lemma is applied as follows. Let v_0  v_1 ⋯  v_n = v be a path of vertices in K from v_0 to v and choose N so large that this path of vertices is contained in the interior of K_i, for all i ≥ N. The Ring Lemma applied sequentially to the chain of pairwise tangent circles in 𝒞_i corresponding to the path v_0  v_1 ⋯  v_n = v implies that there is a positive constant 𝔠 such that R_i(v) ≥𝔠  R_i(v_0), where R_i is the Euclidean radius function on 𝒞_i.  This holds for all i ≥ N and the constant 𝔠 is independent of i. As hyperbolic and Euclidean radii of circles in the disk are comparable in the small, this implies the claim.
  
  Now order the vertex set V(K) as v_0, v_1, …. In case (I), choose a subsequence i_j so that the hyperbolic centers of the circles of the sequence 𝒞_i_j all corresponding to the vertex v_1 converge in the closed disk 𝔻 to a point c_1. An application of item (ii) of the Discrete Schwarz Pick Lemma implies that c_1 is contained in the open disk 𝔻. Repeat to find a subsequence of i_j for which the hyperbolic centers of the circles corresponding to v_2 converge to a point c_2 in 𝔻. Iterating and applying a diagonal argument gives a subsequence of the sequence of circle packings 𝒞_i for which the hyperbolic centers of the circles corresponding to the vertex v_n of K converges to a point c_n in 𝔻 for all positive integers n. Centering a circle of hyperbolic radius 𝔯(v_n) at the point c_n produces a circle packing in the Poincaré disk in the pattern of K. In case (II) when 𝔯 is identically zero, a diagonal argument applied to the scaled packing 1/R_i𝒞_i, where R_i is the Euclidean radius of C_i, produces a circle packing in the plane ℂ in the pattern of K. Call the limit circle packing in either case 𝒞.
  
  There are three facts left to prove: first, that 𝒞 is univalent; second, that 𝒞 fills the disk in case (I) and the plane in case (II); third, that 𝒞 is unique up to automorphisms. The first claim of univalence follows from the fact that each circle packing 𝒞_i is univalent and the convergent subsequence of radii and centers described above essentially describes geometric convergence of circle packings. Beardon and Stephenson's original proof of the second claim that the packing fills 𝔾 relied critically on the bounded degree assumption. It was used to ensure that piecewise linear maps from the complexes K_i into the geometry 𝔾 defined using the convergent sequence of circle packings are uniformly quasiconformal so that the Carathéodory Kernel Theorem <cit.> applies to ensure that the image of the limit function is the kernel of the image sets, which is the whole of 𝔾. The third claim of uniqueness in the hyperbolic case (I) follows from the uniqueness of the limiting radius function, but in the Euclidean case (II), uniqueness uses the bounded degree assumption. Later He and Schramm removed the bounded degree assumption. Their proof of uniqueness in case (II) is particularly elegant. It is a topological proof based on the winding numbers of  mappings defined on the boundaries of corresponding intersticial regions in two circle packings for the same complex K, both of which fill ℂ. All of this is rather nicely laid out in Stephenson's Introduction to Circle Packing <cit.>.
  
  
  
  
  
  
   §.§ Types of type.
   The dichotomy between hyperbolic and Euclidean behavior is evident in the Discrete Uniformization Theorem. Indeed, the combinatorial complex K, or its 1-skeleton 𝒯, determines uniquely its geometry in that the maximal circle packing 𝒯(𝒞) fills either the disk 𝔻 or the complex plane ℂ, but forbids two packings where one fills the disk and the other the plane. This leads to the next definition.
  [cp-type]
  	A simplicial triagulation K of the plane, and its 1-skeleton plane triangulation graph 𝒯 = K^(1), are said to CP-parabolic or CP-hyperbolic when the maximal circle packing 𝒯(𝒞) fills respectively the complex plane ℂ or the disk 𝔻. The CP-type problem is the problem of determining whether a given complex K or plane triangulation graph 𝒯 is CP-parabolic or CP-hyperbolic. One seeks conditions or invariants on the complex K or the graph 𝒯, reasonably checked or computed, that can determine which of the two CP-types adheres. See <Ref>.
  
  This is a discrete version of the classical conformal type problem, or just type problemcircle packing!type problem for short, that of determining whether, à la classical Uniformization Theorem, a given non-compact simply connected Riemann surface is parabolic and conformally equivalent to the complex plane ℂ, or hyperbolic and conformally equivalent to the disk 𝔻. 
  
  
  
  
  Historically this is not the first discrete type problem. That honor probably goes to the  problem of determining the random walk type, or RW-type for short, of an infinite graph. My aim in this section is to review this and several other species of discrete type problems and explore their interactions in the context of plane triangulation graphs. In all I will examine six different species of discrete type that go under the abbreviations CP, RW, EL, EEL, VEL, and EQ-type.
  
  Consider the standard simple random walk on a simple, connected, locally finite  graph 𝒢 where the probability of walking across a particular edge uv from vertex u to vertex v is 1/  u. The graph 𝒢 is said to be random walk parabolic, or RW-parabolic, if a walker almost surely returns to a fixed base vertex, and random walk hyperbolic or RW-hyperbolic otherwise. More common terminology is that the graph is recurrent when RW-parabolic and transient when RW-hyperbolic. In a transient graph, a random walker has a positive probability for escaping to infinity whereas in a recurrent one, the escape probability vanishes and, in fact, the walker almost surely returns to every vertex infinitely often. Woess <cit.> is a fantastic reference for the classical theory of random walks on graphs and Lawler and Limic <cit.> is an up-to-date reference with many recent results.
  
  Early on in the development of circle packing theory, Ken Stephenson made a connection between the CP- and RW-type problems. The intuition for the connection arises from the close connection in classical complex function theory between the conformal type problem and brownian motion on a Riemann surface. Stephenson <cit.> proved that the CP- and RW-types of bounded degree plane triangulation graphs always coincide. Later in <cit.>, He and Schramm gave an example of a plane triangulation graph, necessarily of unbounded degree, that is CP-parabolic but RW-hyperbolic. There the authors focused more sharply on the distinction between these two species of type and recalled Duffin's EEL-type from <cit.> and developed Cannon's VEL-type inspired by <cit.> in articulating the distinction. 
  
  Before continuing with the discussion of CP-type, let's review a bit of history. The story of discrete type really begins in the nineteen-twenties with Póyla's study <cit.> of the RW-type of the integer grid in ℝ^d where he proved that the integer grid in ℝ^2 is RW-parabolic while the grid in higher-dimensional Euclidean spaces is RW-hyperbolic. In 1959, Nash-Williams in <cit.> used a method of Lord Rayleigh to link the RW-type of a locally finite graph with its resistance to electric flow when each edge is thought of as a wire with a unit of electrical resistance, giving rise to EL-type. To be a bit less cryptic, when an infinite graph is thought of as an electric network with each edge representing a wire of unit resistance, the question is whether electricity will flow from a base vertex to infinity when a unit potential is applied to the base vertex and infinity is grounded. This is made a bit more precise by asking what the effective resistance is from the base vertex to infinity for the network. When the effective resistance to infinity is infinite, no current flows and the network is EL-parabolic, and when the resistance is finite so that current does flow, the network is EL-hyperbolic. In the beautiful 1984 Carus Mathematical Monograph <cit.> entitled Random Walks and Electric networks, Peter Doyle and J. Laurie Snell present an accessible proof that the RW- and EL-type of an infinite graph coincide. In 1962, Duffin <cit.> gave a combinatorial invariant of a graph, the edge extremal length, that characterizes the RW- or EL-type according to whether the edge extremal length of the set of transient edge-paths is infinite or not. 
  
  What is the edge extremal length of a path family? It is a discrete version of the classical conformal extremal length of a path family in a Riemann surface in quasiconformal analysis. For a graph 𝒢, let Γ be any family of edge-paths, infinite or not. The edge extremal length is obtained by measuring the minimal length-squared of the curves in Γ divided by the area, this maximized over all metric assignments. This is the same as the classical definition, only what changes is how the admissible metrics are assigned. Here are the details. An edge-path in 𝒢 is a finite or infinite sequence 𝐞 = e_1, e_2, … of directed edges of 𝒢 with the terminal vertex of e_i equal to the initial vertex of e_i+1. An edge metric on 𝒢 is a function m: E(𝒢) → [0, ∞] that assigns a non-negative value to each edge, and the area of m is defined as area (m) = ∑_e∈ E(𝒢) m(e)^2. An edge metric is admissible if its area is finite and I will let M_E (𝒢) denote the collection of admissible edge metrics. The m-length of the edge-path 𝐞 is ℓ_m(𝐞) = ∑_i=1 m(e_i). Finally, the edge extremal length of the family Γ of edge-paths is
  
      EEL(Γ) = sup_m∈ M_E(𝒢)inf_𝐞∈Γℓ_m(𝐞)^2/area(m).
  
  The notation EEL(𝒢) is reserved for the case where Γ is the set of paths to infinity that start at a given base vertex v_0. These are called the transient edge-paths in 𝒢 based at v_0, and any such transient edge-path 𝐞∈Γ has initial vertex v_0 at its first edge e_1 and is not contained in any finite collection of edges. One says that the graph 𝒢 is EEL-parabolic if EEL(𝒢) = ∞ and EEL-hyperbolic otherwise. It is an easy exercise to confirm that EEL-type does not depend on which base vertex is chosen. Duffin's result of <cit.> already mentioned is that both the RW- and EL-type of a graph coincides with the EEL-type. This was the state of the art in discrete type in the early nineteen-nineties when Stephenson connected CP-type with RW-type for bounded degree plane triangulation graphs. 
  
  In 1995, He and Schramm <cit.> in a remarkable article clarified the role of the bounded degree assumption. There, after constructing a plane triangulation graph that, though CP-parabolic, is RW-hyperbolic, they applied Cannon's vertex extremal length to characterize CP-type combinatorially in the way that edge extremal length characterizes RW-type. Cannon <cit.> introduced the vertex extremal length of a discrete curve family made of shinglings and used it as a tool for assigning combinatorial moduli to ring domains in the space at infinity of a negatively curved group. He and Schramm adapted Cannon's vertex extremal length to Duffin's development of EEL-type to create VEL-type. The adjustment merely replaces edge-paths by vertex-paths and edge metrics by vertex metrics. The vertex extremal length of a family Δ of vertex paths is 
  
      VEL(Δ) = sup_m∈ M_V(𝒢)inf_𝐯∈Δℓ_m(𝐯)^2/area(m).
  
  Here, a vertex-path is a sequence 𝐯 = v_1, v_2, … where each v_i is incident with its successor v_i+1, and a vertex metric is a non-negative function m:V(𝒢) → [0,∞] with area area (m) = ∑_v∈ V(𝒢) m(v)^2. The m-length of the vertex-path 𝐯 is ℓ_m(𝐯) = ∑_i=1 m(v_i) and the set of admissible metrics, the ones of finite area, is denoted as M_V(𝒢). The VEL-type of 𝒢 now is defined analogously to EEL-type. Indeed, VEL(𝒢) means VEL(Δ), where Δ is the set of transient vertex-paths based at v_0, those that meet infinitely many vertices. The graph 𝒢 is VEL-parabolic if VEL(𝒢) = ∞ and VEL-hyperbolic otherwise, and again it is an easy exercise to confirm that VEL-type does not depend on which base vertex is chosen. This seemingly innocuous adjustment to the definition of EEL-type turns out to be precisely the tool needed to characterize CP-type.
  
  Though, easily, the EEL- and VEL-types of a bounded degree graph coincide, they may differ for a graph of unbounded degree. The relationships between the four types—RW, EL, EEL, VEL—are summarized in the next theorem.
  
   Let 𝒢 be a connected, infinite, locally finite graph. 
  	
  		
    (i)[Nash-Willliams <cit.>, Duffin <cit.>] The three types—RW, EL, EEL—coincide for 𝒢.
  		
    (ii) [He-Schramm <cit.>] If 𝒢 is EEL-parabolic then it is VEL-parabolic. If 𝒢 has bounded degree and is VEL-parabolic, then it is EEL-parabolic. 
  		
    (iii) [He-Schramm <cit.>] There is a VEL-parabolic plane triangulation graph that is EEL-hyperbolic, necessarily of unbounded degree.
  	
  
  
  For a plane triangulation graph 𝒯, all five types—RW, EL, EEL, VEL, CP—coincide provided 𝒯 has bounded degree. As stated above, it was Stephenson who first proved this for RW- and CP-types. He and Schramm clarified the need for the bounded degree hypothesis, and the relationship between discrete types for plane triangulation graphs is summarized next.
  [He-Schramm <cit.>]
  	Let 𝒯 be a plane triangulation graph. Then 𝒯 is CP-parabolic if and only if it is VEL-parabolic. 
  
  
  The proofs of these theorems are quite difficult and involved, though still elementary, and space forbids any sort of discussion of the proofs that would do justice to the subject. Suffice it to say that the interested reader can do no better than to consult the references cited in this section to fill in gaps in the desired detail of proofs.
  
  The Discrete Type Theorem for Plane Triangulation Graphs reduces the very difficult problem of determining whether the maximal circle packing for 𝒯 is parabolic or hyperbolic to a combinatorial computation on the graph 𝒯. The disappointment comes when one actually tries to do the computation of VEL(𝒯) from Equation <ref> for almost any given plane triangulation graph. One then finds out just how difficult it is to perform this  computation; nonetheless, this development is useful for some theoretical considerations. For example, He and Schramm use the theorem to extend Stephenson's result on RW- and CP-type. Here is an interesting result of the author that uses the computation of Equation <ref> for the proof of item (ii) of the theorem. 
  
  [Bowers <cit.>] Let 𝒢 be a connected, infinite, locally finite graph and 𝒯 a plane triangulation graph.
  
  	
    (i) If 𝒢 is Gromov negatively curved and its Gromov boundary  contains a nontrivial continuum, then 𝒢 is RW-hyperbolic.
  	
    (ii) If 𝒯 is Gromov negatively curved, then 𝒯 is CP-parabolic if and only if its Gromov boundary is a singleton; alternately, it is CP-hyperbolic if and only if its Gromov boundary is a topological circle.
  	
  
  
  I refer the reader to the appendix of the article <cit.> for definitions and basic theorems on Gromov negatively curved graphs and metric spaces. To show how the computation from Equation <ref> may proceed, I'll prove the lemma used in <cit.> to prove the first assertion of item (ii) of Theorem <ref>.
  
  
  Let v_0 be a vertex in the connected, infinite, locally finite graph 𝒢 and let {V_n} be a sequence of pairwise disjoint sets of vertices, each of which separates v_0 from infinity. Suppose there exist positive constants C and ε such that, for n ≥ N,
  
      Card (V_n) ≤ Cn.
  
  Then the graph 𝒢 is VEL-parabolic.
  
  
  
  Define the vertex metric m by m(v) = 1/ (nlog n) for any v∈ V_n when n≥ N, and m(v) =0 otherwise. Then m is admissible since
  
      area(m) = ∑_n=N^∞Card(V_n)/(n log n)^2≤∑_n=N^∞C/n(log n)^2 < ∞.
  
  For any transient vertex-path 𝐯, the m-length satisfies ℓ_m (𝐯 ) ≥∑_n=N^∞ 1/ (n log n) = ∞, hence every transient vertex-path has infinite m-length. This implies that VEL (𝒢) = ∞ and 𝒢 is VEL-parabolic.
  
  I'll end this section with a sixth version of discrete type that is of recent interest in several settings. It arose first for me when Ken Stephenson and I constructed expansion complexes of finite subdivision rules, for the first time in <cit.> when examining the pentagonal subdivision rule of Cannon, Floyd, and Parry <cit.>. More recently it arises in our examination of hierarchical conformal tilings <cit.>, and in Gill and Rohde's <cit.> examination of random planar maps. I name this version of discrete type EQ-type with EQ an abbreviation for equilateral. A plane triangulation graph 𝒯 = K^(1) can be used to build a piecewise equilateral surface by setting each edge to unit length and isometrically gluing unit-sided equilateral triangles along their boundaries to the boundaries of the faces of K. This produces a piecewise flat surface |𝒯|_eq that has a natural conformal atlas obtained as follows. Each edge e of 𝒯 indexes a chart map φ_e defined on the interior of the union of the faces incident with e. These have been identified with unit equilateral triangles and the chart map φ_e is an orientation-preserving isometry to the plane ℂ. Each vertex v also indexes a chart map φ_v defined on the metric neighborhood of v in |𝒯|_eq of radius 1/2, and uses an appropriate complex power mapping to flatten that neighborhood to a disk in the plane ℂ. The overlap maps are conformal homeomorphisms between the appropriate domains. The chart family 𝒜 = {φ_x : x ∈ V(𝒯) ∪ E(𝒯)} forms a complex atlas making |𝒯|_eq into a non-compact simply connected Riemann surface S(𝒯). The type problem now is manifest. Is S(𝒯) conformally the plane ℂ or the disk 𝔻? In the former case, 𝒯 and K are said to be EQ-parabolic, in the latter EQ-hyperbolic.
  
  
  Notice that the question of the EQ-type of a plane triangulation graph is the classical question of the conformal type of a simply connected Riemann surface. It bares the moniker discrete because of how the surface is built—using discrete building blocks, the equilateral triangles, glued in a combinatorial pattern encoded in 𝒯. The desire is for a combinatorial invariant of 𝒯 or K that will determine its EQ-type. So, what relationship exists between the discrete types already discussed and EQ-type? For plane triangulation graphs of bounded degree, easy arguments using quasiconformal mappings show that EQ-type coincides with CP-type—just map the equilateral triangle in |𝒯|_eq at face f to the corresponding geodesic triangle in 𝔾. When 𝒯 has bounded degree, this map is uniformly quasiconformal and so the EQ-type agrees with the conformal type of 𝔾. For unbounded degree plane triangulation graphs, it remains an open question as to whether the EQ-type coincides with, say, the EEL- or the VEL-type, or perhaps neither. I am bold enough to offer the following conjecture.
  
  
  For any plane triangulation graph, EQ-type coincides with VEL-type, and therefore with CP-type.
  
  
  A great reference for various expressions of discrete type and their stability under subdivision is Bill Wood's doctoral thesis <cit.> and the subsequent article <cit.>. I now turn our attention to Koebe's original inspiration for his circle packing theorem, his interest in circle domains, uniformization, and the Kreisnormierungsproblem.
  
  
  
   §.§ Koebe uniformization for countably-connected domains.
  Koebe uniformization conjecture!for countably-connected domains
  Zheng-Xu He and Oded Schramm's work on circle packing in the late nineteen-eighties and early nineteen-nineties led them to a study of Koebe's Uniformization Conjecture. Though the discrete circle packing tools they developed and used did not directly apply to Koebe's problem, the perspective they had gained turned out to be useful. By 1992-93, they had made the greatest advance on Koebe's problem since its articulation and had proved a circle packing version that greatly generalized the Discrete Uniformization Theorem. Their work is detailed in the Annals of Mathematics article Fixed points, Koebe uniformization, and circle packings. The proofs are rather intricate and so I am content to state the two main results without any indication of the proofs, leaving it to the interested reader to peruse <cit.> for details.
  
  [He and Schramm <cit.>, Schramm <cit.>]
  Every countably connected domain in the Riemann sphere is conformally homeomorphic to a circle domain. Moreover, the circle domain is unique up to Möbius transformations and every conformal automorphism of the circle domain is the restriction of a Möbius transformation.
  
  
  A domain triangulation graph is the 1-skeleton of a simplicial triangulation of a planar domain. 
  
  [He and Schramm <cit.>]
  Every domain triangulation graph with at most countably many ends has a univalent circle packing in the plane ℂ whose carrier is a circle domain. Moreover, the circle packing is unique up to Möbius transformations.
  
  
  He and Schramm prove a theorem that generalizes their Uniformization Theorem to generaized domains and generalized circle domains. This more general unifomization theorem then is used to give a quick proof of their Discrete Uniformization Theorem. 
  
  I'll close this section by mentioning that Schramm in a 1995 paper <cit.> introduced the notion of transboundary extremal length that generalizes the classical extremal length of curve families. Transboundary extremal length is more suited to path families in multiply connected domains that allow for the curves of the family to pass through the complementary components of the domain. Using this tool, Schramm gives a short proof of Koebe uniformization of countably connected domains and generalizes it in two ways. First, he shows that circle domains as the target of uniformization may be replaced by more general domains, namely, those where the complementary components are what he calls τ-fat sets. Second, he shows that some domains with uncountably many complementary components may be uniformized to circle domains, namely those where the complementary components are uniformly fat. This includes for example domains whose boundary components are points and μ-quasicircles for a fixed constant μ≥ 1.
  
  
  
  
  
  
  
  § SOME THEORETICAL APPLICATIONS.
  
  The theoretical work in circle packing has grown up hand-in-hand with various applications. In the past score of years, the needs of computer imaging have added a practical bent to the applications with the use of the theory for everything from medical imaging to 3D-printer head guidance. This has been one of the impetuses for the development of the discipline of discrete differential geometry with discrete conformal geometry as but one of its chapters. Circle packing theory à la Thurston as described in this article is one flavor of this, but several groups of computational geometers and computer scientists have developed discrete conformal geometry in a great variety of ways, with new techniques designed to solve both practical and theoretical problems. The discipline has grown to a vast enterprise too large and complicated for a review of this type. Rather than attempt a thorough discussion of these applications, I'll only mention a couple of the theoretical applications. The first  stands as one of the linchpins of the discipline, and the second generalizes the first. I'll leave it for the interested reader to peruse the many resources available to learn of the state of the art today in practical applications.
  
  
  
  
  
   §.§ Approximating the Riemann mapping.
  
  The event that really got circle packing launched, piquing the interest of a small group of research mathematicians from as diverse fields as complex function theory, combinatorial and computational geometry, geometric topology, and the classical theory of polyhedra, was Bill Thurston's address entitled The Finite Riemann Mapping Theorem at Purdue University in 1985. He presented there an algorithm for computing discrete versions of the Riemann mapping of a fixed, proper, simply connected domain in the complex plane ℂ to the unit disk 𝔻, with an indication of why the discrete mappings should converge to a conformal homeomorphism of the domain onto 𝔻. Burt Rodin and Dennis Sullivan published in <cit.> a proof of Thurston's claims in 1987, and this began a steady output of published research on circle packings that continues today. Here I review the content of Thurston's 1985 talk and explain the Rodin-Sullivan verification of Thurston's claims.
  
  Thurston's algorithm is illustrated nicely in the graphics of  <Ref>.
  
  The scheme is rather simple. Overlay a domain D with a hexagonal circle packing ℋ_ε of constant circle radii ε, a `penny packing.'  Use the domain D as a cookie cutter to cut out a portion of the packing, say 𝒫_ε, whose combinatorics are given by the simplicial complex T_ε. Apply the Maximal Disk Packing Theorem to obtain a maximal circle packing 𝒬_ε of the disk 𝔻. Choosing two points x and y in the domain D, let u_ε and v_ε be the vertices of T_ε whose corresponding circles are closest to the respective points x and y. From the uniqueness of the Maximal Disk Packing Theorem, one may assume that the packings 𝒬_ε have been normalized so that the circle corresponding to u_ε is centered at the origin and the one corresponding to v_ε is centered on the positive real axis. Define the discrete Riemann mappingdiscrete Riemann mapping f_ε : carr(𝒫_ε) →carr(𝒬_ε) as the piecewise linear mapping that takes centers of circles of 𝒫_ε to corresponding centers of circles of 𝒬_ε. Thurston's claim of his 1985 lecture that Rodin and Sullivan verified in 1987 is the content of the next theorem.
  
  [Rodin and Sullivan <cit.>]
  The mappings f_ε converge as ε↓ 0, uniformly on compact subsets of D, to the Riemann mapping f of D onto 𝔻 with f(x) = 0 and f(y) > 0.
  
  
  Before I discuss the proof, I should say that there is nothing special about the hexagonal combinatorics. He and Schramm <cit.> verified that the particular combinatorics of the overlay packings are irrelevant as long as the maximum circle radii approach zero.
  
  
  The proof applies classical tools from quasiconformal analysis to confirm convergence of the discrete mappings to the Riemann mapping. There are three parts. First, the Ring Lemma, already used on page RingLemma in the proof of the Discrete Uniformization Theorem, is used to observe that the discrete Riemann mappings f_ε for ε > 0 form a  family of uniformly quasiconformal mappings with, say, dilatation of all maps bounded by μ≥ 1. Second, standard results of quasiconformal analysis imply that the mappings converge to a μ-quasiconformal mapping f of D onto 𝔻. Third, the limit mapping is proved to be 1-quasiconformal, or just conformal, so that it is a Riemann mapping of the domain D onto the disk 𝔻. Allow me to fill in each of the three parts of the argument a bit.
  
  The first part, that the discrete Riemann mappings have quasiconformal distortion uniformly bounded, uses the fact that simplicial homeomorphisms are μ-quasiconformal with the distortion constant μ depending only on the shapes of the triangles involved. In particular, because the complexes T_ε have constant degree six on interior vertices, the Ring Lemma implies that there is a minimum possible angle ω > 0 for any of the triangles in the Euclidean carrier carr(𝒬_ε), this independent of ε. This implies that the discrete maps f_ε are uniformly μ-quasiconformal since the images of the equilateral triangles of carr(𝒫_ε) are triangles of carr(𝒬_ε) of uniformly bounded distortion. 
  
  The second part now follows from standard tools of quasiconformal analysis. The uniformly quasiconformal maps f_ε are equicontinuous on compact subsets of D, as are the maps f_ε^-1 on compact subsets of 𝔻. It follows that the family {f_ε}_ε >0 is a normal family and any limit mapping f is bijective between D and 𝔻. This latter claim uses the fact that any limit mapping is necessarily μ-quasiconformal, and the Carathéodory Kernel Theorem implies that f takes D onto 𝔻.
  
  Finally, that any limit mapping f is conformal follows from the Hexagonal Packing Lemma. This says that in a packing with hexagonal combinatorics, any two adjacent circles buried deeply within the packing have nearly equal radii. Here is the exact statement.
  
  [Rodin and Sullivan <cit.>]
  There is a sequence c_n decreasing to zero as n→∞ such that in any packing with n generations of the regular hexagonal combinatorics surrounding circle C, the ratio of radii of C and any adjacent circle differs from unity by less than c_n. 
  
  
  This lemma shows that as ε↓ 0, the mappings f_ε restricted to a fixed compact subset of D maps equilateral triangles to triangles of carr(𝒬_ε) that become arbitrarily close to equilateral, and this implies that any limit mapping is conformal.
  
  This completes the proof modulo the proof of the Hexagonal Packing Lemma. This is proved as follows. Let H_n be any packing of circles in the plane with combinatorics given by greater than or equal to n generations of the hexagonal packing and whose central circle is the circle C_0 of unit radius centered at the origin. The Ring Lemma implies that the radii of the circles n generations removed from C_0 in the packings H_m for m≥ n are bounded away from zero and infinity. A diagonal argument implies that there is a subsequence H_n_i that geometrically converges to a packing H, which necessarily has hexagonal combinatorics. But the uniqueness of the Discrete Uniformization Theorem implies that H = ℋ_1, the penny packing of unit radius. If the lemma were not true, one could choose the sequence H_n in such a way that the ratio of the center circle of H_n to at least one of its neighbors differs from unity by at least a fixed constant δ > 0. This would imply that the limit packing H has a circle adjacent to C_0 of non-unit radius, contradicting uniqueness.
  
  I should mention that Rodin and Sullivan did not have access to the Discrete Uniformization Theorem in 1987 as it was published only in 1990. They had to prove uniqueness of the penny packing of the plane, which they did by invoking results of Dennis Sullivan <cit.> extending the Mostow Rigidity Theorem to non-compact three-manifolds whose volumes grow slowly enough. This initiated an attempt to prove the Hexagonal Packing Lemma using only elementary means, which ultimately led to a better understanding of the rigidity of infinite circle packings over the next decade. This paper of Rodin and Sullivan was highly influential and can claim to be the genesis of the serious study of circle packings that now includes in its accomplishments hundreds of articles, thousands of citations, and a huge reservoir of applications in a great variety of different settings.
  
  
  
   §.§ Uniformizing equilateral surfaces.
  equilateral surface
  I already have defined piecewise equilateral metrics determined by plane triangulation graphs in the context of the type problem. Of course there is nothing special about plane triangulation graphs. Any triangulation T of a surface may be endowed with a piecewise equilateral metric by identifying faces with unit equilateral triangles. Exactly as explained in Section <ref>, this endows the surface with a complex atlas of conformal charts indexed by the vertices and edges of the triangulation. Equilateral surfaces have become important in several different areas of mathematics. They arise for example in Grothendieck's theory of dessins d'enfants and their corresponding Belyĭ maps, see <cit.>, in Angel and Schramm's theory of uniform infinite planar triangulations <cit.>, in Gill and Rohde's study of random planar maps <cit.>, in Bowers and Stephenson's theory of conformal tilings and especially those that arise from expansion complexes <cit.>, and in discrete conformal flattening of surfaces in ℝ^3 <cit.>. In this section I introduce a method of uniformizing these surfaces using the tools of Rodin-Sullivan <cit.> and basic surface theory.
  
  Let T be a triangulation of the topological surface S. The notation |T|_eq is used to denote the piecewise equilateral metric space determined by the triangulation T and 𝒮_T to denote the Riemann surface determined by the atlas 𝒜 = {φ_x : x ∈ V(T) ∪ E(T)}. Note that T need not be a simplicial triangulation for this to make sense. A face f of T first is identified as an equilateral triangle in |T|_eq and then as a curvilinear triangle in the canonical metric of constant curvature on the surface 𝒮_T. What is the shape of f in 𝒮_T? One fact about the shape of this curvilinear triangle is that the angle that two of its sides makes that emanate from the same vertex is 2π /d, where d is the degree of the vertex. Another fact is that the sides are analytic arcs, and in fact any such arc is the fixed point set of an anti-conformal reflection that exchanges the two triangles incident with that arc. In the case 𝒮_T is parabolic or hyperbolic, f can be lifted to the plane ℂ or the Poincaré disk 𝔻 and so this shape may be displayed as a curvilinear triangle in the plane. In case 𝒮_T is elliptic, this shape may be stereographically projected from the 2-sphere to the plane. How does one get at this shape? The answer Ken Stephenson and I supplied in <cit.> is the content of this section.
  
  For simplicity, let's restrict our attention to closed surfaces. The scheme for approximating a uniformizing map is to use the triangulation T as a pattern for a circle packing, and then refine iteratively using so-called hex-refinement to obtain a sequence 𝒫_n of finer and finer circle packings, after an initial barycentric subdivision. Hex-refinement applied to a triangular face just adds a vertex to each existing edge and then connects the three new vertices on the three edges of the face by a 3-cycle of edges, thus subdividing the face into four smaller triangles.
  
  
  
  
  
  Thus barycentric subdivision followed by hex-refinement produces T_1, and iteration of hex-refinement then produces the sequence T_n with 𝒫_n the corresponding circle packing in the surface 𝒮_n in the pattern of T_n. There is an added layer of difficulty here in that, unlike with the use of the hexagonal packing in the Discrete Riemann Mapping Theorem, the circle packings in this setting do not occupy the same surface. The surfaces 𝒮_n are determined by the triangulations T_n according to Theorem <ref>, and these need not be conformally equivalent to one another. Also, any face f of T with nth hex-subdivision f_n in T_n determines a sequence 𝒫_n(f) of circle packings, those circles in 𝒫_n corresponding to the vertices of f_n.
  
  [Bowers and Stephenson <cit.>]
  The surfaces 𝒮_n converge in moduli as n→∞ to a surface 𝒮 that is conformally homeomorphic to the surface 𝒮_T, the Riemann surface determined by the equilateral surface |T|_ eq. For any face f of T, the carriers of 𝒫_n(f) converge geometrically to the shape of f in 𝒮_T when given its canonical constant curvature metric.
  
  
  The latter statement of the theorem may be understood to mean that when one lifts the carriers to the universal cover, the sphere 𝕊^2, the plane ℂ, or the disk 𝔻, and normalizes appropriately, the carriers converge in the Hausdorff metric on compacta to the appropriate lift of f in 𝒮_T.
  
  
  Note that the realizations of the triangulation T in the metric surface |T|_eq and in the Riemann surface 𝒮_T are reflective, meaning that each edge e is the fixed point set of an anti-conformal reflection that exchanges the two faces contiguous to e.[To be clear, the reflection is anti-conformal on the interior of the union of the two faces incident at e, but not at the vertices.] Rather than the canonical constant curvature metric, I shall use the piecewise equilateral metric ρ_T on 𝒮_T throughout the proof. Here is a key observation. Hex-subdivision may be performed metrically in 𝒮_T by adding new vertices v(e) as the mid-points of the edges e∈ E(T) and connecting v(e) to v(e') by a Euclidean straight line segment in the metric ρ_T in the face bounded by edges e, e' and e”. This realizes the hex-refined triangulation T_1 as a reflective triangulation in 𝒮_T.[Technically, this is after the initial barycentric subdivision, which also is performed in the metric ρ_T and yields a reflective triangulation.] Iterating, T_n may be realized as a reflective triangulation of 𝒮_T that metrically hex-subdivides T_n-1.
  
  Define homeomorphisms h_n : 𝒮_T→𝒮_n so that the image of vertex v of T_n under h_n is the center of the circle that corresponds to v in the circle  packing 𝒫_n, extend linearly along edges and then with minimum quasiconformal distortion across faces. By the Ring Lemma, each mapping h_n is quasiconformal, and since hex-refinement does not increase degree, any bound ≥ 6 on the degrees of the vertices of T also bounds the degrees of the vertices of T_n, for all n ≥ 1. This implies that the homeomorphisms h_n have uniformly bounded dilatations, and this implies that a subsequence of the surfaces 𝒮_n converges in moduli to a Riemann surface 𝒮.  
  
  My claim is that 𝒮 is conformally equivalent to 𝒮_T. This would be confirmed were the maximum dilatations of the homeomorphisms h_n shown to limit to unity as n→∞, but unfortunately this does not occur. In fact these dilatations are bounded away from unity with large dilatations concentrated near the original vertices of T. To get around this, let D be a compact domain in 𝒮_T disjoint from the vertex set V(T). Note that the combinatorics of T_n away from the vertices of T is hexagonal, and this implies that as n→∞, the compact set  D is surrounded by a number of generations of the hexagonal combinatorics that increases without bound. The Hexagonal Packing Lemma applies to confirm that the maximum dilatations of the restrictions of the homeomorphisms h_n to D converge to unity. This works for every compact domain that misses the vertex set V(T), and this implies that the limit mapping h :𝒮_T→𝒮 is conformal on the complement of the vertex set V(T). Now the removability of isolated singularities comes into play and implies that the homeomorphism h is conformal at the vertices, and so is a conformal homeomorphism of 𝒮_T onto 𝒮.
  
  
  
  
  <Ref> shows an example of an approximation to a portion of an equilateral surface uniformized in the plane. In this figure each edge is the fixed point set of an anti-conformal reflection that exchanges the grey-white pair of triangles sharing that edge. This is an approximation of the conformally correct shapes of the equilateral triangles forming the equilateral surface being imaged. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § INVERSIVE DISTANCE CIRCLE PACKINGS.
  circle packing!inversive distance Around 2001, Ken Stephenson and I began thinking about inversive distance circle packings and how they could be used to uniformize piecewise flat surfaces, those surfaces in which each face is identified with a flat Euclidean triangle, not necessarily equilateral. There is a tentative discussion of this in <cit.> and further discussion in <cit.> of the difficulties in proving convergence of discrete mappings to the uniformization mapping, though the method does seem to work well in practice; again see <cit.>. The first theoretical questions concern (1) the existence of circle packings with prescribed inversive distances between adjacent circles and (2) the rigidity and uniqueness of these packings. 
  
  When all inversive distances lie in the unit interval, adjacent circles overlap with specified angle 0≤θ≤π/2. This is covered by the Koebe-Andre'ev-Thurston Theorems. When inversive distance is greater than unity, the circles do not overlap and the inversive distance is a Möbius-invariant measure of how separated the circles are. In this case Problems (1) and (2) seem much more difficult to approach. Problem (1) is especially difficult in that there are local assignments of inversive distances that must be avoided as there are no circle configurations that realize those distances. These are difficult to catalogue, but even if there are no local obstructions to the existence of a packing, it is not at all clear whether still there may be global obstructions. Little progress has been made on Problem (1), but the situation for Problem (2) has enjoyed some progress, initially in 2011 and more recently in the past couple of years. It is these recent successes in approaching Problem (2) that occupies this section. My contention is that a change of viewpoint can be effective in approaching inversive distance circle packings, and a hint as to how to proceed comes from the  classical rigidity theory of bar-and-joint linkages. After a brief review of inversive distance, I will explore this new framework for circle packings and discuss some recent successes.
  
  
  
  
  
   §.§ A quick introduction to inversive distance.
  
  There are a number of ways to define the inversive distance between two circles in the Riemann sphere. I will present several of these below, starting with the most mundane that gives a Euclidean formula for the inversive distance between two planar circles.[This easily can be extended to the inversive distance between a circle and a line, or two lines. I will forgo this development since the next definition is completely general.] Let C_1 and C_2 be distinct circles in the complex plane ℂ centered at the respective points p_1 and p_2, of respective radii r_1 and r_2, and bounding the respective companion disks D_1 and D_2. 
  
  [inversive distance in the euclidean metric]
  The inversive distance ⟨ C_1, C_2⟩ between C_1 and C_2 is
  
      ⟨ C_1, C_2⟩ = |p_1-p_2|^2 - r_1^2 - r_2^2/2r_1r_2.
  
  The absolute inversive distance between distinct circles is the absolute value of the inversive distance.
  
  
  The absolute inversive distance is a Möbius invariant of the placement of two circles in the plane. This means that there is a Möbius transformation of ℂ taking one circle pair to another if and only if the absolute inversive distances of the two pairs agree. The important geometric facts that make the inversive distance useful in inversive geometry and circle packing are as follows. When ⟨ C_1,C_2⟩ > 1, D_1∩ D_2 = ∅ and ⟨ C_1,C_2⟩ = coshδ, where δ is the hyperbolic distance between the totally geodesic hyperbolic planes in the upper-half-space model ℂ× (0,∞) of ℍ^3 whose ideal boundaries are C_1 and C_2. When ⟨ C_1,C_2⟩ = 1, D_1 and D_2 are tangent at their single point of intersection. When 1 >⟨ C_1,C_2⟩≥ 0, D_1 and D_2 overlap with angle 0 < θ≤π/2 with ⟨ C_1,C_2⟩ = cosθ. In particular, ⟨ C_1,C_2⟩ = 0 precisely when θ = π/2. When ⟨ C_1,C_2⟩ < 0, then D_1 and D_2 overlap by an angle greater than π/2. This includes the case where one of D_1 or D_2 is contained in the other, this when ⟨ C_1,C_2⟩≤ -1. In fact, when ⟨ C_1,C_2⟩ < -1 then ⟨ C_1,C_2⟩ = - coshδ where δ has the same meaning as above, and when ⟨ C_1,C_2⟩ = -1 then C_1 and C_2 are `internally' tangent. When -1 < ⟨ C_1,C_2⟩ <0, then the overlap angle of D_1 and D_2 satisfies π > θ > π/2 and again ⟨ C_1,C_2⟩ = cosθ. 
  
  The more general definition measures the inversive distance between oriented circles. Note that an oriented circle determines a unique closed companion or spanning disk that the circle bounds. Indeed, assuming fixed orientations for 𝕊^2 and ℂ that are compatible via stereographic projection, the companion disk determined by the oriented circle C is the closed complementary disk D (of the two available) whose positively oriented boundary ∂^+ D = C, where of course the orientation of D is inherited from that of 𝕊^2 or ℂ. This is described colloquially by saying that D lies to the left of C as one traverses C along the direction of its orientation. 
  
  [general inversive distance]
  Let C_1 and C_2  be oriented circles in the extended plane ℂ bounding their respective companion disks D_1 and D_2, and let C be any oriented circle mutually orthogonal to C_1 and C_2.  Denote the points of intersection of C with C_1 as z_1,z_2 ordered so that the oriented sub-arc of C from z_1 to z_2 lies in the disk D_1.  Similarly denote the ordered points of intersection of C with D_2 as w_1,w_2.  The general inversive distance between C_1 and C_2, denoted as ⟨ C_1,C_2⟩, is defined in terms of the cross ratio
  
      [z_1,z_2;w_1,w_2]=(z_1-w_1)(z_2-w_2)/(z_1-z_2)(w_1-w_2)
  
  by
  
      ⟨ C_1,C_2⟩ =2[z_1,z_2;w_1,w_2]-1.
  
  Subsequently, I'll drop the adjective general and refer to the inversive distance ⟨ C_1, C_2⟩ with its absolute value |⟨ C_1, C_2⟩ | the absolute inversive distance.[The author first learned of defining inversive distance in this way from his student, Roger Vogeler. He has looked for this in the literature and, unable to find it, can only surmise that it is original with Prof. Vogeler. The definition appeared in <cit.> in 2003.]
  
  
  
  
  
  Recall that cross ratios of ordered 4-tuples of points in ℂ are invariant under Möbius transformations and that there is a Möbius transformation taking an ordered set of four points of ℂ to another ordered set of four if and only if the cross ratios of the sets agree.  This implies that which circle C orthogonal to both C_1 and C_2 is used in the definition is irrelevant as a Möbius transformation that set-wise fixes C_1 and C_2 can be used to move any one orthogonal circle to another.  Which one of the two orientations on the orthogonal circle C is used is irrelevant as the cross ratio satisfies [z_1,z_2;w_1,w_2]=[z_2,z_1;w_2,w_1].  This equation also shows that the inversive distance is preserved when the orientation of both circles is reversed so that it is only the relative orientation of the two circles that is important for the definition. In fact, the general inversive distance is a relative conformal measure of the placement of an oriented circle pair on the Riemann sphere. By this I mean that two oriented circle pairs are inversive equivalent if and only if their inversive distances agree. All of this should cause one to pause to develop some intuition about how companion disks may overlap with various values of inversive distances. See <Ref> for some corrections to possible misconceptions. Finally, the inversive distance is symmetric with ⟨ C_1,C_2⟩  = ⟨ C_2,C_1⟩ since [z_1,z_2;w_1,w_2]=[w_1,w_2;z_1,z_2]. 
  
  
  
  
  
  The inversive distance is real since the cross ratio of points lying on a common circle is real and, in fact, every real value is realized as the inversive distance of some oriented circle pair. Notice that if the orientation of only one member of a circle pair is reversed, the inversive distance merely changes sign.  This follows from the immediate relation [z_1,z_2;w_2,w_1]=1-[z_1,z_2;w_1,w_2]. Despite its name, the inversive distance is not a metric as it fails to be non-negative and fails to satisfy the triangle inequality.[Some authors, perhaps more aptly, call the inversive distance the inversive product of C_1 and C_2.]
  
   The third definition is entirely in terms of the spherical metric.
   
  [inversive distance in the spherical metric]
  In the 2-sphere 𝕊^2, the inversive distance may be expressed as
  
      ⟨ C_1, C_2⟩ = -cos∢ ( p_1,p_2 ) + cos(r_1) cos(r_2)/sin(r_1) sin(r_2) =- p_1· p_2  + cos(r_1) cos(r_2)/sin(r_1) sin(r_2).
  
  Here, ∢ (p_1,p_2) = cos^-1 (p_1· p_2) denotes the spherical distance between the centers, p_1 and p_2, of the respective companion disks, p_1· p_2 the usual Euclidean inner product between the unit vectors p_1 and p_2, and r_1 and r_2 the respective spherical radii of the companion disks. Note that r_i = cos^-1 (p_i· q_i) for any point q_i on the circle C_i, for i=1,2.
  
  
  Verifying the equivalence of this with the general definition is an exercise in the use of trigonometric identities after a standard placement of C_1 and C_2 on 𝕊^2 followed by stereographic projection. This standard placement is obtained by finding the unique great circle C orthogonal to both C_1 and C_2 and then rotating the sphere so that this great circle is the equator, which then stereographically projects to the unit circle in the complex plane. The details are left to the reader.
  
  Here are two more quick descriptions of inversive distance. For those conversant with the representation of circles in 𝕊^2 by vectors in de Sitter space, the inversive distance is the Minkowski inner product between the two points of de Sitter space that represent the two oriented circles. This is, perhaps, the most elegant formulation of the product. The final way I'll describe the inversive distance is a neat little curiosity. Let C_1 = ∂𝔻 = 𝕊^1 be the unit circle oriented clockwise and C_2 a circle oriented counterclockwise that meets the open unit disk non-trivially. Then, as explained on page Page:ConstantCurve, the intersection c_2 of C_2 with the open disk is a curve of constant geodetic curvature in the Poincaré disk 𝔻≅ℍ^2. The inversive distance is ⟨ C_1,C_2⟩ = curv(c_2), the geodetic curvature of the cycle c_2 in the Poincaré metric on 𝔻. This includes all three cases for the cycle c_2—a hyperbolic circle in 𝔻, a horocycle that meets ∂𝔻 at a single point, or a hypercycle that meets ∂𝔻 at two points.[My student, Opal Graham, noticed, then proved this when I was lecturing on the curves of constant geodetic curvature in the hyperbolic plane.]
   
   
  
  
  
  
  
   §.§ Some advances on the rigidity question.
   In <cit.>, inversive distance circle packings were introduced. Rather than preassigned overlap angles labeling edges of a triangulation of a surface as in the Koebe-Andre'ev-Thurston Theorems, preassigned inversive distances label the edges. As stated already, questions of interest are of the existence and uniqueness of circle configurations in geometric structures on surfaces that realize the inversive distance data. Though the existence question is wide open, in 2011-12 there were three advances on the uniqueness question for inversive distance packings. First, Guo <cit.> proved that inversive distance packings of closed surfaces of positive genus, ones supporting flat or hyperbolic metrics, are locally rigid whenever the inversive distances are non-negative. Shortly after that, Luo <cit.> improved this to global rigidity, or uniqueness of the packings in the cases considered by Guo. Then in a surprising result of the year following, Ma and Schlenker <cit.> produced a counterexample to global uniqueness for packings of the 2-sphere. They gave examples of pairs of circle packings of 𝕊^2 in the pattern of the octahedral triangulation with six circles that satisfy the same inversive distance data, but that are not Möbius equivalent.
  
  
  The ingredients of Ma and Schlenker's example are Schönhardt's twisted octahedron, which is an infinitesimally flexible polyhedron in Euclidean space 𝔼^3, embeddings in de Sitter space 𝕊^3_1, and special properties of the Pogorelov map between different geometries. In 2017, John Bowers and I <cit.> constructed a large family of Ma-Schlenker-like examples using only inversive geometry, producing many counterexamples to the uniqueness of inversive distance circle packings in the 2-sphere.
  
  The Schönhardt octahedron is an example of a bar-and-joint linkage important in the rigidity theory of Euclidean frameworks, and its use in the Ma-Schlenker example hinted at a way forward in understanding the rigidity theory of inversive distance circle packings in the 2-sphere. This led to a fruitful change in viewpoint and a reformatting of the question of uniqueness of inversive distance circle packings to the question of the rigidity—local, global, and infinitesimal—of more general circle frameworks. These are  
  analogues in Möbius geometry of the Euclidean frameworks in Euclidean geometry with point configurations in 𝔼^3 replaced by circle configurations in 𝕊^2 and the Euclidean metric replaced by the non-metric inversive distance. The analogy is not exact, but the theory of linkages in 𝔼^3 has been found to be a good guide for understanding some of the rigidity theory of circle frameworks. Part of why this works so well is because the space of circles in the 2-sphere is a 3-dimensional incidence geometry that has much in common with the space of points in Euclidean 3-space. The lines of this geometry are coaxial circle families and the planes are what Carathéodory in <cit.> called bundles of circles. This allows one to define what is meant by a convex collection of circles, planar collections of circles, circle polyhedra, bounded circle configurations, etc. Space constraints in this article interfere with even a cursory account of these issues, so I am content with listing a couple of recent successes of the theory without all the definitions needed for a precise understanding, and then taking some time to set up the language of this change of viewpoint.
  
  The two theorems following are the result, both the statements and the proofs, of an engagement between circle packing theory and the classical rigidity theory  of Euclidean frameworks in 𝔼^3.
  
  [Bowers, Bowers, and Pratt <cit.>]
  	Let 𝒞 and 𝒞' be two non-unitary, inversive distance circle packings with ortho-circles for the same oriented edge-labeled triangulation of the 2-sphere 𝕊^2. If 𝒞 and 𝒞' are convex and proper, then there is a Möbius transformation T:𝕊^2→𝕊^2 such that T(𝒞) = 𝒞'. 
  
  
  The edge-label refers to prescribed inversive distances labeling each edge. 
  Non-unitary means that the inversive distance between any pair of adjacent circles is not unity; in fact, these inversive distances are in the set (-1,1)∪(1, ∞). Having ortho-circles means that each triple of mutually adjacent circles have an orthogonal circle. This generalizes to a global rigidity theorem about circle polyhedra, circle configurations in the pattern of 3-dimensional polyhedra whose faces correspond to circle configurations that are planar in the incidence geometry of circle space; see <cit.> for details.
  
  [Bowers, Bowers, and Pratt <cit.>]
  	Any two convex and proper non-unitary circle polyhedra with Möbius-congruent faces that are based on the same oriented abstract spherical polyhedron and are consistently oriented are Möbius-congruent.
  
  
  Theorem <ref> coupled with the Ma-Schlenker example of <cit.> and the examples of <cit.> show that the uniqueness of inversive distance circle packings, and more generally, of circle polyhedra is exactly analogous to that of Euclidean polyhedra—convex and bounded polyhedra in 𝔼^3 are prescribed uniquely by their edge lengths and face angles whereas non-convex or unbounded polyhedra are not. The proof of this for convex and bounded Euclidean polyhedra is Cauchy's celebrated rigidity theorem <cit.>, which is reviewed in Section <ref>. The proof of Theorem <ref> follows Cauchy's original argument, which splits the proof into two components—a combinatorial lemma and a geometric lemma. Cauchy's combinatorial lemma deals with a certain labeling of the edges of any graph on a sphere, and applies to the present setting. The geometric lemma, known as Cauchy's Arm Lemma, requires that a polygon with certain properties be defined for each vertex of the polyhedron, and fails to apply here. The main work of the proof is in describing and analyzing a family of hyperbolic polygons called green-black polygons that are defined for each vertex of a circle polyhedron in a Möbius-invariant manner. An analogue of Cauchy's Arm Lemma for convex green-black polygons is developed and used to to prove these theorems.
  
  
  
   §.§ Circle frameworks and Möbius rigidity.
   I'll close out this section with a description of the change in viewpoint from circle packings to circle frameworks. This can be done using only absolute inversive distance, but I find it advantageous to remain as general as possible in setting up the viewpoint. The goal is to generalize the language of circle packings and patterns of triangulations and quadrangulations of the 2-sphere to that of circle realizations of oriented circle frameworks. Let G be a graph, by which I mean a set of vertices V= V(G) and simple edges E = E(G). Both loops and multiple edges are disallowed. An oriented edge incident to the initial vertex u and terminal vertex v is denoted as uv, and -uv means the oppositely oriented edge vu. I will use the same notation, uv, to denote an un-oriented edge, context making the meaning clear. A circle framework with adjacency graph G, or c-framework for short, is a collection 𝒞 = { C_u : u ∈ V(G) } of oriented circles in 𝕊^2 indexed by the vertex set of G. This is denoted by G(𝒞). Two c-frameworks G(𝒞) and G(𝒞') are equivalent if ⟨ C_u, C_v⟩ = ⟨ C_u', C_v'⟩ whenever uv is an edge of G. Let H be a subgroup of the inversive group Inv(𝕊^2) of the 2-sphere. Two collections 𝒞 and 𝒞' of oriented circles indexed by the same set are H-equivalent or H-congruent provided there is a mapping T∈ H such that T(𝒞) = 𝒞', respecting the common indexing and the orientations of the circles. When H is not so important they are inversive-equivalent or inversive-congruent, and when T can be chosen to be a Möbius transformation, they are Möbius-equivalent or Möbius-congruent. The global rigidity theory of c-frameworks concerns conditions on G or G(𝒞) that ensure that the equivalence of the c-frameworks G(𝒞) and G(𝒞') guarantees their H-equivalence. Often one restricts attention to c-frameworks in a restricted collection ℱ of c-frameworks. In Theorem <ref>, ℱ is the collection of non-unitary, convex and proper c-polyhedra and the interest is in Möbius equivalence.
  
  [labeled graph and circle realization]
  	An edge-label is a real-valued function β : E(G) →ℝ defined on the edge set of G, and G together with an edge-label β is denoted as G_β and called an edge-labeled graph. The c-framework G(𝒞) is a circle realization of the edge-labeled graph G_β provided ⟨ C_u, C_v⟩ = β (uv) for every edge uv of G, which henceforth is denoted as G_β(𝒞). See <Ref>.
  
  
  
  
  
  Circle packings are circle realizations of edge-labeled graphs that arise as the 1-skeletons of oriented triangulations of the 2-sphere that also satisfy certain properties that ensure that the realizations of the triangular boundaries of faces respect orientation. The general definition allows for branch vertices and configurations of circles in which the open geodesic triangles cut out by connecting centers of adjacent circles overlap. There are subtleties in which I have no interest, so I am going to adapt a restricted definition that corresponds to the circle packings that arise from spherical polyhedral metrics on triangulated surfaces. These are circle realizations of the edge-labeled 1-skeleton G_β= K^(1)_β of an oriented triangulation K of 𝕊^2 that produce oriented geodesic triangulations[By this I mean that the orientation of the geodesic triangulation determined by the packing is consistent with the orientation on K.] of the 2-sphere when adjacent circle centers are connected by geodesic arcs. The assumption here is that the centers of no two adjacent circles are antipodal, so that there is a unique geodesic arc connecting them, and that the centers of three circles corresponding to the vertices of a face of K do not lie on a great circle. Now this causes no particular problems when all adjacent circles overlap nontrivially, the traditional playing field of circle packing, but does cause some real concern when adjacent circles may have inversive distance greater than unity. For example, a circle realization may produce a geodesic triangulation of the sphere by connecting adjacent centers while its Möbius image may not. This is traced directly to the fact that neither circle centers nor radii, nor geodesic arcs, are Möbius invariants in the inversive geometry of the sphere. This behavior does not occur for inversive distance circle packings of the Euclidean or hyperbolic planes (and surfaces), precisely because circle centers and geodesics are invariant under automorphisms and radii are invariant up to scale in Euclidean geometry and invariant in hyperbolic geometry. My belief is that using centers and radii of circles in inversive geometry should be avoided except where these can be used to simplify computations (as in the use of the spherical definition of inversive distance). The shift then is from inversive distance circle packings to inversive distance circle realizations. One is less concerned with possible underlying geodesic triangulations and more concerned with Möbius-invariant quantities. For example, rather than working with a geodesic face formed by connecting the centers of three mutually adjacent circles, one is more interested in the existence of an ortho-circle, a circle mutually orthogonal to the three, which is a Möbius invariant. Though the initial motivation was circle packing as reflected in Theorem <ref>, the real interest has evolved to circle realizations as reflected in the more general version represented by Theorem <ref>.
  
  It turns out that Theorem <ref> has implications for the rigidity of generalized hyperbolic polyhedra in ℍ^3. Thurston was the first to exploit this connection between circle configurations on 𝕊^2 and hyperbolic polyhedra in ℍ^3 in really significant ways, and his observations inspired several avenues of clarification and generalization. It is to this that I turn in the penultimate section of this article.
  
  
  
  
  
  
  
  § POLYHEDRA—FROM STEINER (1832) TO RIVIN (1996), AND BEYOND
  polyhedron
  In this section I survey the rich mathematical vein that has been mined in the geometric theory of polyhedra, particularly of three-dimensional hyperbolic polyhedra, that has its origins in Thurston's insights on using his circle packing theorem to characterize certain hyperbolic polyhedra. The initial observation of Thurston was that the study of polyhedra in hyperbolic three-space can be transferred to the study of overlapping circle packings in the two-sphere by realizing the Riemann sphere as the boundary of the Beltrami-Klein model of ℍ^3 sitting as the unit ball 𝔹^3 in the real projective three-space. Theorems in one of these venues correspond to theorems in the other. Later Thurston's students, Oded Schramm and Igor Rivin, made great strides in the theory of both 3-dimensional Euclidean and hyperbolic polyhedra, not so much using the techniques of circle packing but instead using very intricate and clever geometric arguments, often times in this classical setting of ℍ^3≅𝔹^3⊂𝔼^3⊂ℝℙ^3. There is here a beautiful interplay among the classical geometries illustrating Arthur Cayley's aphorism that “All geometry is projective geometry.” Here one sees the Beltrami-Klein model of hyperbolic three-space as a sub-geometry of the real projective three-space, with its orientation-preserving isometry group naturally identified with the Lorentz group of Minkowski space-time, which itself restricts to the two-sphere boundary of hyperbolic space as the group of circle-preserving transformations of the two-sphere, the group of Möbius transformations. This one geometry, the real projective geometry of dimension three, presents a playing field for studying three-dimensional polyhedra—classical Euclidean polyhedra, hyperbolic polyhedra of various types and generalizations, projective polyhedra, and circle polyhedra of Möbius geometry. 
  
  I will begin with an application of Thurston's circle packing theorem on using  polyhedra to cage a sphere, and move then to Schramm's generalization. From there I will discuss the characterization of certain hyperbolic polyhedra—compact by Hodgson and Rivin, ideal by Rivin, and hyper-ideal by Bao and Bonahon—and will finish with very recent work by Chen and Schlenker that characterizes those convex projective polyhedra all of whose vertices lie on the ideal boundary of hyperbolic space. I include a bonus final section on Cauchy's 1813 Rigidity Theorem for the reader who is approaching this subject as a novice. This is the fundamental theorem of rigidity theory, and the techniques and tools Cauchy developed have been used time and again in proofs of rigidity in the past two hundred years. Both Schramm and Rivin make use of Cauchy's toolbox in their theorems on convex hyperbolic and Euclidean polyhedra, as do Bao and Bonahon as well as Bowers, Pratt and the author. Before these recent developments, previous generations of mathematicians who delved into the study of polyhedra made use of Cauchy's toolbox—Dehn in his proof of infinitesimal rigidity, Aleksandrov in his rigidity results, Gluck in his examination of generic rigidity, and Connelly in various of his contributions.
  
  
  
  
  
   §.§ Caging eggs—Thurston and Schramm.
   In 1832, Jakob Steiner <cit.> asked 
  
  In which cases does a convex polyhedron have a combinatorial equivalent which is inscribed in, or circumscribed about, a sphere?
  polyhedron!inscribed or circumscribed
  When a convex polyhedron P is inscribed in the sphere S so that its vertices lie on S, then its polar dual circumscribes the sphere S, so that each face of the dual P^* meets S in a single point. It wasn't until 1928 that Ernst Steinitz found families of non-inscribable polyhedral types with the example of a cube truncated at one vertex being the simplest. Marcel Berger <cit.> (p. 532) takes this long duration of time between Steiner and Steinitz as evidence that the theory of polyhedra in the years intervening had fallen into disrespect among mathematicians, being a subject of the old-fashioned mathematics of synthetic geometry.[Berger <cit.> uses the word disdain to describe the prevailing opinion of the study of polyhedra.] One would be hard pressed to say that the study of polyhedra in the time between Steinitz and Thurston was anything but a curiosity to many a mathematician schooled in the rarified heights of abstraction that had captured the mathematical mind of the time. The sort of “pedestrian geometry” offered by the study of polyhedra captured the imagination of a select few. There has been a healthy development of the rigidity theory of polyhedra, notably by Aleksandrov in the nineteen-fifties, and Gluck and Connelly in the nineteen-seventies. Aleksandrov's work was largely ignored in the West until the nineteen-eighties. Coxeter had done truly foundational work in the combinatorial structure of polyhedra in the nineteen-forties and -fifties, and Victor Klee and Branko Grünbaum began their foundational studies a bit later. Coxeter's work in geometry was routinely dismissed by much of mainstream mathematics as old-fashioned nineteenth century mathematics, uninteresting and pedestrian. Both Aleksandrov and Coxeter were “rehabilitated” by the larger community of geometers and topologists when their work of the forties and fifties—Aleksandrov's on metric geometry and Coxeter's on reflection groups—became important to the development of geometric group theory after Gromov's publication of his hyperbolic groups essay <cit.> in 1987. With apologies to Aleksandrov, Coxeter, Klee, and Grünbaum, it has taken the attention of Thurston and his students Schramm and especially Rivin to resurrect more intense interest among topologists in this venerable old subject of classical geometry.[Grünbaum <cit.> addresses the disinterest of the mathematical community in the combinatorial theory of polytopes in the preface to his book.]
  
  Steinitz's basic tool for attacking the Steiner question is the following observation. Suppose the polyhedron P circumscribes the sphere S. Let e = uv be an edge of P with adjacent faces f and g. Since P circumscribes S, the face f is tangent to S at a point p and g is tangent at a point q. Then the angle ∠ upv = ∠ uqv in measure and we let Θ (e) denote this common value. It is immediate that summing these edge labels for the edges of any face yields an angle sum of 2π. The reader might want to use this observation to see why a dodecahedron truncated at every vertex admits no inscribed sphere as there is no edge labeling Θ for this polyhedron that satisfies this property.
  
  According to Steinitz then, the condition that an edge label Θ: E(P) → (0,π) exists for the polyhedron P whose sum for the edges of each face is 2π is a necessary condition that P have a combinatorially equivalent realization that circumscribes a sphere, but it is not sufficient. It was not until Rivin's study of hyperbolic polyhedra in the late nineteen-eighties and early -nineties that a characterization of polyhedra of circumscribable type, ones combinatorially equivalent to polyhedra that may circumscribe a sphere, was found. The definitive result is due to Rivin and reported in Hodgson, Rivin, and Smith <cit.>, and follows from his characterization of ideal convex hyperbolic polyhedra that is presented in a later section.
  
  [Rivin]
  A polyhedron P is of circumscribable type if and only if there exists a label Θ: E(P) → (0,π) such that the sum of the labels Θ(e) as e ranges over any circuit bounding a face is 2π, while the sum as e ranges over any simple circuit not bounding a face is strictly greater than 2π.
  
  A polyhedron is of inscribable type if it is combinatorially equivalent to one that may be inscribed in a sphere.
  [Rivin]
  
  A polyhedron P is of inscribable type if and only if its dual P^* is of circumscribable type.
  
  
  The proofs will be discussed later, but first I want to generalize this discussion a bit. Inscription and circumscription are the respective cases, m=0 and m=d-1, of the question of whether a d-dimensional convex polytope has a realization in 𝔼^d each of whose m-dimensional faces meets a fixed (d-1)-dimensional sphere in a single point. One says that the polytope is (m,d)-scribable in this case. Egon Shulte <cit.> proved in the mid-nineteen-eighties that when 0≤ m < d and d > 2, then there are combinatorial types of d-dimensional polytopes that are not (m,d)-scribable, except for the single exceptional case when (m,d) = (1,3). The exceptional case then is when a convex polyhedron in 𝔼^3 midscribespolyhedron!midscribe a sphere S, so that each edge of P is tangent to S, meeting S in exactly one point.
  
  In light of Shulte's result it perhaps is surprising that in his exceptional case, every convex polyhedron in 𝔼^3 has a combinatorially equivalent realization that is midscribable about, say, the unit sphere 𝕊^2. Thurston in Chapter 13 of GTTM states that this is a consequence of Andre'ev's theorems in <cit.>. The proof I give merely applies the Koebe-Andre'ev-Thurston Theorem to an appropriately edge-labeled graph.
  
  [Thurston <cit.>]
  Every convex polyhedron in 𝔼^3 has a combinatorially equivalent realization that is midscribable about the unit sphere 𝕊^2. Considering 𝔼^3⊂ℝℙ^3, any such realization is unique up to projective transformations of ℝℙ^3 that set-wise fix the unit sphere 𝕊^2.[The projective transformations that  fix 𝕊^2 act as Möbius transformations on 𝕊^2.]
  
  
  
  
  
  Let P be a convex polyhedron in 𝔼^3 and let K be the simplicial 2-complex obtained by adding a vertex to each open face of P and starring to the vertices. Precisely, the vertices of K are those of P along with a new vertex v_f for each face f of P. The edges are the edges of P along with edges of the form vv_f, where v is a vertex of f. The faces are the 2-simplices of the form uvv_f where uv is an edge of f. Write the edge-set of K as E(K) = E(P) ∪ E', where E' are the new edges of the form vv_f. Define an angle map Φ : E(K) → [0,π/2] by Φ(e) = 0 when e∈ E(P) and Φ(e) = π/2 when e ∈ E'. An application of the Koebe-Andre'ev-Thurston Theorem I produces a circle packing K(𝒞) on the 2-sphere 𝕊^2  and a geodesic triangulation in the pattern of K with overlap angles of adjacent circles given by Φ. For each face f of P, let H_f be the half-space in 𝔼^3 that meets all the circles of K(𝒞) and whose bounding plane ∂ H_f contains C_v_f. My claim is that the convex polyhedron Q = ∩_f ∈ F(P) H_f midscribes 𝕊^2 and is combinatorially equivalent to P.
  
  For any vertex v of P, let v^* be the apex of the cone in 𝔼^3 that is tangent to 𝕊^2 along the circle C_v, and when e = uv is an edge of P, let e^* = u^*v^* be the segment with endpoints u^* and v^*. Let f be a face of the polyhedron P with vertices v_1, …, v_n written in cyclic order. Since the circle C_v_f is orthogonal to the circles C_v_i, the apexes v_i^* all lie on the bounding plane ∂ H_f, for i=1, …, n. Let f^* denote the convex hull of the points v_1^*, …, v_n^* in ∂ H_f. A moment's thought should convince the reader that the convex polyhedron Q may be described as the convex hull of the set V(Q) = { v^* : v∈ V(P)}. It follows that the vertex set of Q is V(Q), edge set is E(Q) = { e^* : e∈ E(P)}, and face set is F(Q) = { f^* : f ∈ F(P) }. This verifies that P and Q are combinatorially equivalent. Moreover, the edge e^* = u^* v^* is tangent to the sphere 𝕊^2 at the point of intersection of the circles C_u and C_v, which are tangent since Φ (e) = 0. Hence Q midscribes the sphere 𝕊^2. See <Ref>.
  
  Uniqueness up to projective transformations that fix the unit sphere follows from the Möbius uniqueness of the circle packing K(𝒞) with edge angle data Φ and the fact that the Möbius group extends its action on 𝕊^2 to a projective action of ℝℙ^3 set-wise fixing 𝕊^2.
  
  
  Schulte introduced in <cit.> the question of whether the sphere can be replaced by other convex bodies. Schramm <cit.> proved that when the convex polyhedron P is simplicial, then for any smooth convex body S, a combinatorially equivalent polyhedron Q exists that midscribes S. Of course this means that each edge of Q is tangent to the boundary ∂ S. Shortly thereafter, Schramm improved his result by removing the requirement that P be simplicial. A convex body S is strictly convex if its boundary contains no non-degenerate line segment, and is smooth if each point of the boundary has a unique supporting plane. This latter condition is equivalent to the boundary being C^1-smooth. Schramm's definitive result on midscription is the main theorem of his Inventiones article <cit.> whimsically entitled How to cage an egg.
  
  [Schramm <cit.>]
  	Let P be a convex polyhedron and S a smooth strictly convex body in 𝔼^3. Then there exists a convex polyhedron Q combinatorially equivalent to P that midscribes S. 
  
  
  
  The proof is rather involved and so I am content to give the briefest of indication of its method. Schramm defines the configuration space 𝒵 = (𝔼^3)^V(P)×G(2,3)^F(P), where V(P) and F(P) are the respective sets of vertices and faces of P, and G(2,3) is the manifold of oriented affine planes in 𝔼^3. In this way P is identified with a single point of 𝒵, and the combinatorial type of P defines a submanifold 𝒵_P of 𝒵 corresponding to various convex polyhedra in 𝔼^3 that are combinatorially equivalent to P. Schramm then shows that there is a C^2 convex body S_0 with positively curved boundary that P midscribes. Let S_t, 0≤ t ≤ 1, be a C^2-path of convex bodies with positively curved boundaries with S_1 = S. The idea now is to flow S_0 to S_1 along this path and drag combinatorial realizations of P along as midscribing polyhedra. The proof relies on a fine analysis of the configuration space 𝒵 and its submanifold 𝒵_P, and the method is to show that when S_t is midscribed by a realization of P, then so is S_t' for all t' in an open interval about t. Then a delicate argument shows also that the set of parameter values for which S_t is midscribable by a realization of P is a closed set. Being open and closed, and nonempty since P midscribes S_0, this set of parameter values must be the whole of the unit interval, hence S=S_1 is midscribed by a realization of P.
  
  
  The remaining discussion on hyperbolic polyhedra has little to do, at least directly, with the Koebe-Andre'ev-Thurston Theorem. The arguments tend to be clever and technical, but ultimately involve the elementary geometry of hyperbolic space, often times realized as the unit ball in projective 3-space where the machinery of the Minkowski inner product and of de Sitter space is available. I include the discussion in order to complete for the reader the current state of affairs in the study of convex hyperbolic polyhedra, a study which I view as having been revitalized by Thurston's articulation of KAT I and pushed forward into the broader mathematical consciousness by the seminal work of Thurston's students, Oded Schramm and especially Igor Rivin.
  
   
  
  
   §.§ Compact and convex hyperbolic polyhedra—Hodgson and Rivin.
  polyhedron!compact and convex hyperbolic In his doctoral thesis of 1986, Igor Rivin studied convex hyperbolic polyhedra. Therein he gave a characterization of compact, convex hyperbolic polyhedra that generalizes the Andre'ev results of <cit.>[See Roeder, Hubbard, and Dunbar's paper <cit.> for a readable proof of Andre'ev's classification of compact hyperbolic polyhedra with non-obtuse exterior dihedral angles.], and in articles in the early nineteen-nineties, extended his characterization to ideal polyhedra, generalizing Andre'ev's results in <cit.>. He used this latter generalization to answer definitively Steiner's question of 1832 asking for a characterization of those polyhedra that circumscribe a sphere. This of course is the content of the Circumscribable Type Characterization Theorem of the preceding section. In this section, I present an overview of Rivin's characterization of compact and convex hyperbolic polyhedra in terms of a generalized Gauss map. The overview embellishes Hodgson's outline presented in <cit.> (and repeated in  <cit.>). In the section following, I outline Rivin's characterization of ideal polyhedra and make his observation that the Circumscribable Type Characterization Theorem is an immediate corollary of his characterization of ideal polyhedra.
  
  To lay the groundwork, let's review the Gauss map 𝙶 of a compact and convex Euclidean polyhedron P to the unit sphere 𝕊^2. This is a set-valued map from the 2-complex forming the boundary of P that assigns to the point p of ∂ P the set of outward pointing unit normals to support planes to P at p. Thus when p is a point of an open face f, 𝙶(p) = 𝙶(f) is a single point determined by the outward unit normal to f. When p is in the open edge e incident to faces f and g, 𝙶(p) = 𝙶(e) is the great circular arc connecting 𝙶(f) to 𝙶(g) of length equal to the exterior dihedral angle between f and g. Finally, for a vertex p of P, (p) is the convex spherical polygon bounded by the arcs 𝙶(e) for edges e incident with p. When edges e and e' of the face f are incident at p, the interior angle of the polygon 𝙶(p) at the vertex 𝙶(f) is π - α, where α is the interior angle of the face f at p. In this way the Gauss map realizes the Poincaré dual P^* of P as a geodesic cellular decomposition of the 2-sphere 𝕊^2. Notice that the Gauss map does not encode all the information needed to reconstruct the polyhedron P. It encodes the interior angles of all the faces and the dihedral angles of all adjacent faces, but there is no encoding of side-lengths of the edges of P. For example, all rectangular boxes have the same image under the Gauss map, namely, a regular right-angled octahedral decomposition of the sphere 𝕊^2. 
  
  
  
  Another way to describe the convex spherical polygon 𝙶(p) for a vertex p of P is as the polar dual 𝙻^*(p) of the infinitesimal link 𝙻(p) of p in P.[For a Euclidean polyhedron, 𝙻(p) is the intersection of P with a small sphere centered at p, one whose radius is smaller than the lengths of edges incident with p, rescaled to unit radius, and is oriented so that its interior is “to the left” as one traverses the polygon in its positive direction.] Note that 𝙻(p) is a convex spherical polygon with internal angles equal to the dihedral angles of the faces of P incident with p, and edge-lengths equal to the internal angles at the vertex p in the faces of P incident with p. Recall that an oriented great circle in 𝕊^2 and its spherical center are polar duals of one another. The polar dual 𝙻^*(p) is obtained by replacing the edges of 𝙻(p) by the polar dual centers of their supporting great circles, and the vertices by appropriate arcs of the polar dual great circles. A nice exercise in spherical geometry verifies that 𝙻^*(p) is isometric to 𝙶(p). This gives an alternate construction of the Poincaré dual P^* as a geodesic, cellular decomposition of the 2-sphere—just isometrically glue the polar duals 𝙻^*(p) together as p ranges over the vertices of P along corresponding edges, 𝙻^*(p) glued to 𝙻^*(q) whenever pq is an edge of P.[The edge pq determines respective vertices u and v of 𝙻(p) and 𝙻(q) whose respective polar edges u^* and v^* have the same lengths, namely the exterior dihedral angle of P at edge pq.] Obviously this gluing produces a 2-sphere, not only homeomorphic, but also  isometric to the standard 2-sphere 𝕊^2, and reproduces the cellular decomposition determined by the Gauss map.
  
  It is this latter construction of the Poincaré dual P^* as a cellular decomposition of the 2-sphere that readily generalizes to convex and compact hyperbolic polyhedra. Indeed, let P now be a convex and compact hyperbolic polyhedron in ℍ^3 and for each vertex p, let 𝙻^*(p) be the polar dual of the infinitesimal link 𝙻(p) of p in P.[This is the link in the tangent space of ℍ^3 of the pre-image of the intersection of P with a small neighborhood of p under the exponential map.] The link 𝙻(p), as in the Euclidean case, is an oriented convex spherical polygon in 𝕊^2 with internal angles equal to the dihedral angles of the faces of P incident with p, and edge-lengths equal to the internal angles at the vertex p in the faces of P incident with p. The polar dual 𝙻^*(p) then encodes the exterior dihedral angles at the edges of P incident with p as the lengths of its edges, and the interior angles α of the faces incident with p as its interior angles in the form π - α. This construction acts as a local Gauss map in a small neighborhood of the vertex p. Now exactly as before, isometrically glue the polar duals 𝙻^*(p) together as p ranges over the vertices of P along corresponding edges. The result is again a 2-sphere topologically, which is called the Gaussian image of P and denoted as 𝙶(P), with a spherical metric of constant unit curvature, except at the vertices. The vertices have cone type singularities with concentrated negative curvature. Indeed, at the vertex corresponding to the face f = p_1⋯ p_n of P, the angle sum is θ (f) = nπ - ∑_i=1^nα_i, where α_i is the internal angle of f at the vertex p_i. In the hyperbolic plane, the compact and convex polygon f always has interior angle sum strictly less than (n-2) π so that θ (f) > 2π.
  
  This brings us to Rivin's characterization of compact and convex hyperbolic polyhedra.
  
  [Rivin]
  A metric space (M, g) homeomorphic to 𝕊^2 can arise as the Gaussian image 𝙶(P) of a compact and convex polyhedron P in ℍ^3  if and only if these three conditions adhere.
  
  
    (i) The metric g has constant curvature +1 except at a finite number of cone points.
  
    (ii) The cone angle at each cone point is greater than 2π.
  
    (iii) The lengths of the nontrivial closed geodesics of (M,g) are all strictly greater than 2π.
  
  Moreover, the metric g determines P uniquely up to hyperbolic congruence.
  
  
  Recall that the Gauss map does not determine Euclidean polyhedra up to congruence since it contains no information about side lengths. In contrast, a hyperbolic polyhedron is determined up to a global hyperbolic isometry by its Gaussian image. The proof of this uniqueness uses Cauchy's toolbox that is reviewed in Addendum <ref>, wherein I recall the tools Cauchy used to prove his celebrated rigidity theorem of 1813. The necessity of items (i) and (ii) follows from the previous discussion and that of (iii) uses the fact that the total geodedic curvature of a non-trivial closed hyperbolic space curve is greater than 2π, a hyperbolic version of Fenchel's Theorem on Euclidean space curves. The proof of sufficiency is based on Aleksandrov's Invariance of Domain method used in his study of Euclidean polyhedra in <cit.>.
  
  Rivin also uses Cauchy's toolbox to prove this rather interesting theorem that illustrates again the enhanced rigidity of hyperbolic polyhedra vis-à-vis Euclidean ones.
  
  [Rivin]
  The face angles of a compact and convex polyhedron in ℍ^3 determine it up to congruence.
  
  
  The characterization of compact and convex hyperbolic polyhedra in terms of the Gaussian image surveyed here suffers from the same defect as Aleksandrov's characterization of compact and convex Euclidean polyhedra. Both characterizations posit a singular positively curved metric on a 2-sphere, but neither provides a way to decode from this metric space (M,g) the combinatorial type of the polyhedron P encoded in (M,g). The proof is not constructive, but depends on a topological analysis within the space of admissible metrics on the 2-sphere satisfying the three conditions of the characterization and yields, finally, the abstract fact of existence of an appropriate polyhedron, without describing its combinatorial type.
  
  
  
  
  
  
  
  
   §.§ Convex ideal hyperbolic polyhedra—Rivin
  polyhedron!ideal
  Rivin turns his attention to convex ideal polyhedra in ℍ^3 in <cit.> where he gives a full characterization in terms of exterior dihedral angles. The characterization begins with an analysis of the exterior dihedral angles of such a polyhedron reported in <cit.> with details in <cit.> that goes as follows. Label each edge e^* of the polyhedron P^* dual to the ideal convex polyhedron P by the exterior dihedral angle θ(e^*) of the corresponding edge e of P. Rivin's argument that these labels satisfy the following conditions is reproduced in the next two theorems.
  
  
    (i) 0 < θ(e^*) <π for all edges e of P.
  
    (ii) If the edges e_1^*, …, e_n^* are the edges bounding a face of P^*, then θ(e_1^*) + ⋯  + θ(e_n^*) = 2π.
  
    (iii) If e_1^*, …, e_n^* forms a simple nontrivial circuit that does not bound a face of P^*, then θ(e_1^*) + ⋯  + θ(e_n^*) > 2π.
  
  Compare these conditions with the hypotheses of the Circumscribable Type Characterization on page CTC. Now Condition (i) is a requirement of convexity and Condition (ii) is seen easily in the upper-half-space model by placing one of the ideal vertices v of P at infinity and observing that the link of v is a convex Euclidean polygon. Indeed, the faces incident with v lie on vertical Euclidean planes whose intersections with the xy-plane cut out a convex Euclidean polygon L(v), and quite easily the sum θ(e_1^*) + ⋯  + θ(e_n^*) is precisely the sum of the turning angles of L(v). Condition (iii) is a consequence of the following discrete, hyperbolic version of Fenchel's Theorem, in this case for closed polygonal curves in ℍ^3.
  
  [Rivin <cit.>]
  The total discrete geodesic curvature of a closed, polygonal, hyperbolic space curve is greater than 2π, unless the vertices are collinear, in which case the total curvature is 2π.
  
  
  
  The total discrete geodesic curvature of the polygonal hyperbolic space curve γ with vertices p_1, …, p_k , p_k+1 = p_1 is ∑_i=1^kα_i, where α_i is the turning angle of γ at p_i. The angle α_i is just the exterior angle at p_i of the triangle τ_i = p_i-1p_ip_i+1. For 2≤ i ≤ k-1, let T_i be the triangle T_i = p_1p_ip_i+1 with internal angles a_i, b_i, and c_i at the respective vertices p_1, p_i, and p_i+1. Note that by considering the triangles τ_i, T_i-1 and T_i with common vertex p_i, the spherical triangle inequality gives
  
      c_i-1 + b_i≥π - α_i  for   3≤ i ≤ k-1,
  
  and
  
      b_2 = π -α_2,    c_k-1 = π - α_k,   and  ∑_i=2^k-1 a_i≥π - α_1.
  
  Recalling that π≥ a_i + b_i + c_i with equality only when p_1, p_i, and p_i+1 are collinear, and then summing, one has 
  
      (k-2)π≥∑_i=2^k-1 (a_i + b_i + c_i ) ≥  kπ - ∑_i=1^kα_i,
  
  with equality only when p_1, …, p_k are collinear.  
  
  
  [Rivin <cit.>]
   	The edge label θ(e^*) of the polyhedron P^* dual to the ideal convex polyhedron P defined above satisfies Conditions (i)–(iii).
  
  
  
  Conditions (i) and (ii) already are verified. For Condition (iii), the circuit e_1^*, …, e_n^* that does not bound a face of P^* corresponds to a chain of contiguous faces f_1, …, f_n in P with f_i∩ f_i+1 = e_i. F = ∪_i=1^n f_i is a hyperbolic surface with boundary and cusps, and can be completed by extending geodesically across the boundary components to a complete immersed surface F in ℍ^3 without boundary. The surface F is an immersed hyperbolic cylinder with both ends of infinite-area. This observation uses the fact that the circuit e_1^*, …, e_n^* does not bound a face of P^*. Let γ be the unique closed geodesic path on the surface F that is freely homotopic to the meridian. The curve γ is immersed in ℍ^3 as a polygonal curve lying on F with turning angles at the edges e_i. But it is easy to see that the turning angle of γ at edge e_i is no more than the exterior dihedral angle of the faces f_i and f_i+1 that meet along e_i. This implies that the sum, θ(e_1^*) + ⋯  + θ(e_n^*), which is the sum of these dihedral angles, is at least as large as the discrete geodesic curvature of γ, which in turn is greater than 2π by an application of the preceding theorem.
  
  Rivin was able to turn this around and prove a converse to the theorem, which gives the following characterization of convex, ideal hyperbolic polyhedra. The existence is proved in <cit.>, uniqueness in <cit.>, and necessity of the three conditions in <cit.>.
  
  [Rivin <cit.>]
  Let P^* be an abstract polyhedron. Then for any label θ: E(P^*) → (0, π) that satisfies Conditions (i)–(iii), there is a convex, ideal hyperbolic polyhedron P in ℍ^3 whose Poincaré dual is P^*, and whose exterior dihedral angles at edges e are given by the values θ(e^*). Moreover, P is unique up to hyperbolic congruence. Conversely, every such polyhedron P satisfies Conditions (i)–(iii) as shown in Theorem <ref>.
  
  
  This characterization also proves the Circumscribable and Inscribable Type Characterizations, answering Steiner's question of 1832. This is because a convex, ideal hyperbolic polyhedron in the Beltrami-Klein projective model of ℍ^3 is represented by a convex Euclidean polyhedron inscribed in the 2-sphere 𝕊^2.
  
  Since Rivin's work of the nineteen-nineties, several topologists and geometers have taken up the mantel and continued to unearth these beautiful gems of discrete geometry. I'll close this survey with the mention of two examples in the next section, the first from the first decade of the new century, and the second of very recent origin.
  
  
  
  
  
   §.§ New millennium excavations
  
  Space constraints forbid too much further development of the topic, but I would be remiss if I didn't mention at least these two beautiful theorems, the first characterizing convex hyperideal hyperbolic polyhedra by Bao and Bonahon, and the second giving a complete answer to Steiner's original question when interpreted as broadly as possible, this time by Chen and Schlenker. I develop just enough of these topics to state the main results, and leave the interested reader the task of perusing the original articles for details of the proofs.
  
  
  
  
    §.§.§ Hyperideal polyhedra—Bao and Bonahon
  polyhedron!hyperideal
  A hyperideal polyhedron in ℍ^3 is a non-compact polyhedron that may be described most easily in the Beltrami-Klein projective model ℍ^3 = 𝔹^3⊂ℝℙ^3 as the intersection with 𝔹^3 of a projective polyhedron all of whose vertices lie outside of 𝔹^3 while each edge meets 𝔹^3. Bao and Bonahon <cit.> classify hyperideal polyhedra up to hyperbolic congruence in terms of their dihedral angles and combinatorial type in much the same vein as Rivin's classification of ideal hyperbolic polyhedra. Note that Bao and Bonahon do allow for the vertices to lie on the sphere 𝕊^2 = ∂𝔹^3 and hence their characterization reduces to Rivin's for ideal polyhedra.
  
  I will state the characterization in terms of conditions on the 1-skeletal graph of the dual polyhedron using Steinitz's famous characterization of those graphs that may serve as the dual graph of a convex polyhedron in 𝔼^3 as precisely the planar, 3-connected graphs. 
  
  [Bao and Bonahon <cit.>]
  Let 𝒢 be a 3-connected graph embedded in 𝕊^2 and θ: E(𝒢) → (0, π). There is a hyperideal polyhedron P in ℍ^3 with dual graph isomorphic with 𝒢 and exterior dihedral angles given by θ if and only if the following conditions are satisfied.
  
  
    (i) If e_1, …, e_n forms a simple nontrivial circuit of edges of 𝒢, then θ(e_1) + ⋯  + θ(e_n) ≥ 2π, with equality possible only if e_1, …, e_n bounds a component of 𝕊^2 - 𝒢.
  
    (ii) If γ = e_1, …, e_n forms a simple path of edges of 𝒢 that connects two vertices of 𝒢 that lie in the closure of a component C of 𝕊^2 - 𝒢, but γ does not lie in the boundary of C, then θ(e_1) + ⋯  + θ(e_n) > π.
  
  Moreover if P' is the projective polyhedron with P' ∩ℍ^3 = P, a vertex v of P' is located on the sphere at infinity of ℍ^3 if and only if equality holds in Condition (i) for the boundary of the corresponding component of 𝕊^2 - 𝒢.
  
  Finally, the hyperideal polyhedron P is unique up to hyperbolic congruence.
  
  
  I should mention that Hodgson and Rivin's <cit.> characterization of compact and convex hyperbolic polyhedra can be applied to appropriate truncated polyhedra associated with those hyperideal polyhedra for which no vertex lies on the sphere at infinity to characterize them.
  
  Define a strictly hyperideal polyhedron to be the intersection of 𝔹^3 with a projective polyhedron P all of whose vertices lie outside the closed unit ball 𝔹^3 = 𝔹^3∪𝕊^2, but all of whose faces meet 𝔹^3. Note that this definition allows that an edge of P may lie entirely outside the closed ball 𝔹^3. These are yet to be characterized, but I mention that the article <cit.> verifies the rigidity of these that are bounded and convex, as long as no edges are tangent to the unit sphere. The proof again uses Cauchy's toolbox.
  
  
  
  
  
    §.§.§ Weakly inscribed polyhedra—Chen and Schlenker
   Recall Steiner's question of which polyhedra inscribe or circumscribe a sphere that Rivin answered. A more faithful translation of Steiner's question from the German is “Does every polyhedron have a combinatorially equivalent realization that is inscribed or circumscribed to a sphere, or to another quadratic surface? If not, which polyhedra have such realizations?” He includes the definition that “A polyhedron P is inscribed to a quadratic surface S if all the vertices of P lie on S,” and further defines that P is circumscribed to S if all of its facets are tangent to S. As before I will concentrate on inscription since polarity relates circumscription to inscription. In the very recent preprint <cit.>, Chen and Schlenker point out that the apparent grammar mistake—inscribed to instead of in S—makes a significant distinction.
  
  Generally Steiner's question has been interpreted to ask about inscription of the polyhedron P to a quadratic surface S in Euclidean space 𝔼^3, and in this setting P is contained in the bounded component of the complement of S, i.e., P is “inside” S, hence the change from inscribed “to” to “in”. But Steiner's question makes sense in projective space as well, and in this setting a polyhedron may be inscribed to a surface without being inscribed in the surface. To be a bit more illustrative, consider the unit sphere 𝕊^2 sitting in 𝔼^3⊂ℝℙ^3. Now 𝕊^2 usually is thought of as the boundary of the open unit ball 𝔹^3 that serves as the projective model of hyperbolic space, and this is what Rivin exploited in his characterization of those polyhedra inscribable in 𝕊^2. But 𝕊^2 is also the boundary of the complement ℝℙ^3 - 𝔹^3, which has a complete metric making it into a model of de Sitter space d𝕊^3. In this setting a projective polyhedron may have its vertices on the sphere 𝕊^2 and yet not lie entirely in the ball 𝔹^3 so that it is inscribed to 𝕊^2, but not inscribed in 𝕊^2 in the usual meaning. Following Chen and Schlenker, I will revise Steiner's terminology to emphasize the difference between inscribed in and inscribed to but not in.
  
  [strong and weak inscription]
  In the real projective space ℝℙ^3, a polyhedron P inscribed to a quadratic surface S is strongly inscribed in S if the interior of P is disjoint from S, and weakly inscribed to S otherwise.
  
  
  Before presenting a characterization of those polyhedra weakly inscribed to a sphere in ℝℙ^3, allow a word about polyhedra inscribed to other quadratic surfaces. This topic has been neglected until rather recently. There are only three quadratic surfaces in ℝℙ^3 up to projective transformations, and these are the sphere, the one-sheeted hyperboloid, and the cylinder. Danciger, Maloni, and Schlenker in <cit.> characterized the combinatorial types of polyhedra that are strongly inscribable in a one-sheeted hyperboloid or in a cylinder, and of course Rivin takes care of those strongly inscribable in a sphere. Chen and Schlenker's work reported here characterizes those polyhedra weakly inscribable to a sphere, and the characterization of those weakly inscribable to the remaining two quadratic surfaces is the subject of current research by Chen and Schlenker. 
  
  [Chen and Schlenker <cit.>]
  	A 3-connected planar graph Γ is the 1-skeleton of a polyhedron P⊂ℝℙ^3 weakly inscribed to a sphere if and only if Γ admits a vertex-disjoint cycle cover by two cycles C_1 and C_2 with the following property. Color edge uv red if u and v both belong to C_1 or both belong to C_2, and color it blue otherwise. Then there is a weight function w : E(Γ) →ℝ such that
  	
  		
    (i) w > 0 on red edges and w< 0 on blue ones;
  		
    (ii) w sums to 0 over the edges adjacent to a vertex v, unless v is the only vertex on C_1 or C_2 (trivial cycle), in which case w sums to -2π over the edges adjacent to v.
  	
  
  
  I end this survey of progress in the characterization of polyhedra since Thurston's observation that every polyhedron type in 𝔼^3 has a realization that midscribes a sphere with a description of the original rigidity theorem of Cauchy that is so instrumental in many of the proofs of the results surveyed here.
  
  
  
  
  
   §.§ Addendum: Cauchy's toolbox
   
  polyhedron!Cauchy rigidity
  In this bonus section I review Cauchy's celebrated rigidity theorem <cit.> of 1813 on the uniqueness of convex, bounded polyhedra in 𝔼^3. The theorem concerns two convex polyhedra with equivalent combinatorics and with corresponding faces congruent. Cauchy's Rigidity Theorem states that the two polyhedra must be congruent globally, meaning that there is a Euclidean isometry of the whole of 𝔼^3 mapping one to the other. Like many of the great theorems of mathematics, the proof is of more importance than the theorem itself. As stated earlier in the introduction to this section, the toolbox Cauchy developed has been instrumental in the past two hundred year development of the theory of polyhedra, especially in its rigidity theory. The proof, though at places clever and even subtle, overall is rather straightforward with a simplicity that belies its importance.  
  
  Cauchy's proof has two components—the one geometric and the other combinatorial. The geometric component is the Discrete Four Vertex Lemma, which follows from an application of Cauchy's Arm Lemma. Denote a convex planar or spherical polygon P merely by listing its vertices in cyclic order, say as P = p_1… p_n. The Euclidean or spherical length of the side p_ip_i+1 is denoted as |p_ip_i+1| and the interior angle at p_i is denoted as ∠ p_i.
  
  
  	Let P = p_1 … p_n and P' = p'_1 … p'_n be two convex planar or spherical polygons such that, for 1≤ i < n, |p_i p_i+1| = |p_i' p_i+1'|, and for 1≤ i < n-1, ∠ p_i+1≤∠  p'_i+1. Then |p_n p_1| ≤ |p_n' p_1'| with equality if and only if ∠  p_i+1  = ∠  p'_i+1 for all 1≤ i < n - 1. 
  
  
  Cauchy's original proof of the lemma had a gap that subsequently was filled by Ernst Steinitz. A straightforward inductive proof, such as the one in <cit.>, relies on the law of cosines and the triangle inequality. 
  
  Now let P and P' be convex planar or spherical polygons with the same number of sides whose corresponding sides have equal length. Label each vertex of P with a plus sign + or a minus sign - by comparing its angle with the corresponding angle in P': if the angle at p_i is larger than that at p_i', label it with a +, if smaller, a -, and if equal, no label at all. Using the Cauchy Arm Lemma, the proof of the following lemma is straightforward. 
  
  
  	Let P and P' be as in the preceding paragraph and label the vertices of P as described. Then either P and P' are congruent, or a walk around P encounters at least four sign changes, from - to + or from + to -.
  
  
  
  	First note that because a polygon is a cycle, the number of sign changes must be even. If no vertex is labeled, then the two polygons are congruent. Assume then that some of the vertices are labeled, but all with the same label. Then Cauchy's Arm Lemma implies that there exists a pair of corresponding edges in P and P' with different lengths, a contradiction. 
  	
  	Assume now that there are exactly two sign changes of the labels of P.  Select two edges p_i p_i+1 and p_j p_j+1 (oriented counter-clockwise) of P such that all of the + signs are along the subchain from p_i+1 to p_j and all of the - signs are along the subchain from p_j+1 back to p_i. Subdivide both edges in two by adding a vertex at the respective midpoints X and Y of p_i p_i+1 and p_j p_j+1. Similarly, subdivide the corresponding edges p'_i p'_i+1 and p'_j p'_j+1 in P' at midpoints X' and Y'. Denote the subchain of P from X to Y by P_+ and the subchain from Y back to X by P_-. Similarly for P'_+ and P'_- in P'. Applying the arm lemma to P_+ and P_+' implies that |X Y| > |X' Y'|, and, similarly, an application to P_- and P'_- implies that |X Y| < |X' Y'|, a contradiction. 
  
  
  This brings us to the combinatorial component of Cauchy's proof. A  nice proof of the following lemma appears in <cit.> and follows from an argument based on the Euler characteristic of a sphere.
  
  
  	Let P be an abstract spherical polyhedron. Then for any labeling of any non-empty subset of the edges of P with + and - signs, there exists a vertex v that is incident to an edge labeled with a + or a - sign for which one encounters at most two sign changes in labels on the edges adjacent to v as one walks around the vertex.
  
  
  
  If two bounded, combinatorially equivalent, convex polyhedra in 𝔼^3 have congruent corresponding faces, then they are congruent by a Euclidean isometry of 𝔼^3.
  
  
  
  Assume that bounded, convex polyhedra P and P' have the same combinatorics and congruent corresponding faces. For each edge of P, label its dihedral angle with a + or a - depending on whether it is larger or smaller than the corresponding dihedral angle in P'. If P and P' are not congruent, Cauchy's Combinatorial Lemma provides a vertex v that is incident to an edge labeled with a + or a - sign, and around which there are at most two sign changes. Intersect P with a small sphere centered at v (one that contains no other vertex of P on its interior) to obtain a convex spherical polygon, and intersect P' with a sphere centered at the corresponding vertex v' and of the same radius. By construction both spherical polygons have the same edge lengths, and the angles between edges are given by the dihedral angles between faces at v and v'. An application of the Four Vertex Lemma implies that there are at least four sign changes, contradicting that there are at most two. It follows that P and P' are congruent. 
  
   
  Both the bounded and convex requirements are necessary. For example, a polyhedron Ĥ in the shape of a cubical house with a shallow pyramidal roof has a cousin Ȟ obtained by inverting the roof. Ĥ is not congruent to Ȟ, though these are combinatorially equivalent with congruent corresponding faces.
  
  
  
  
  
  
  
  § IN CLOSING, AN OPEN INVITATION.
  
  This has been a whirlwind tour through the four decade history of the influence of one theorem brought to prominence by the mathematician we celebrate in this volume. Any result that has spawned such a great body of significant work leaves in its wake a bounty of open questions, problems, conjectures, and possible applications that await the right insights for resolution and explanation. What of the Koebe Uniformization Conjecture, of the question of where EQ-type sits among EEL- and VEL-type, of circle packings that mimic rational functions with arbitrary branching, of the existence and rigidity of inversive distance circle packings, of characterizations of projective polyhedra up to Möbius equivalence generalizing Bao-Bonahon, or of combinatorial rather than metric characterizations of hyperbolic polyhedra of various stripes? I have not covered in this survey the myriad of applications that circle packing has spawned, particularly in the realm of computer graphics and imaging, where each month sees more and more new and original publications. And so I close this tribute to the influence of this one theorem of Bill Thurston with an invitation to any reader who has been captured by the beauty and elegance of the results outlined in this survey to explore further on his or her own the wider discipline of Discrete Conformal Geometry, in both its theoretical and practical bents, and perhaps to add to our understanding and appreciation of this beautiful landscape opened up by the imagination of Bill Thurston. 
  
  
  
  
  
  
  amsplain
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  