Circle packing theorem

Other properties

Relative radii

A result known as the ring lemma controls the sizes of adjacent circles in a Euclidean circle packing. According to the ring lemma, if one circle in a packing is surrounded by a ring of ${\displaystyle d}$ others, then the ratio of the inner circle's radius to the smallest radius of its surrounding circles is at most exponential in ${\displaystyle d}$. More precisely, this ratio is at most ${\displaystyle F_{2d-1}-1}$, where ${\displaystyle F_i}$ denotes the ${\displaystyle i}$th Fibonacci number.

Monotonicity of angles

In the triangle connecting the centers of three mutually tangent circles, the angle formed at the center of one of the circles is monotone decreasing in its radius and monotone increasing in the two other radii. In 1991, Alan Beardon and Kenneth Stephenson described related monotonicity properties of circle packings in the hyperbolic plane that they describe as being a discrete analogue to the Schwarz–Pick theorem in complex differential geometry. They consider any finite circle packing in the hyperbolic plane whose coin graph has the structure of a triangulated disk, and they compare this packing to another packing representing the same graph, obtained by treating the line at infinity of the hyperbolic plane as another circle, tangent to all the circles on the outer boundary of the disk (which become horocycles of infinite radius in the second packing). They prove that in the second packing, each circle's radius is non-decreasing, as is the hyperbolic distance between each pair of centers of tangent circles. If any of the radii or distances is equal, then they all are, and the two packings are congruent.

Ordering by radii

A Koebe ordering is the sequence of vertices of a planar graph, ordered by their radii in a circle packing (larger to smaller). If there are no ties (which can be achieved by performing a Möbius transformation) then in the resulting ordering each vertex has at most five earlier neighbors, matching the worst-case degeneracy of planar graphs. This property has been generalized as the ${\displaystyle d}$-admissibility of the ordering, the maximum number of disjoint paths of at most ${\displaystyle d}$ steps that all start at the same vertex ${\displaystyle v}$, continue through vertices later than ${\displaystyle v}$ in the ordering, and end at a vertex earlier than ${\displaystyle v}$. Any Koebe ordering has ${\displaystyle d}$-admissibility ${\displaystyle O(d/\log d)}$, best possible for planar graphs to within a constant factor.

Triangulated packings of surfaces

Instead of starting with a topological embedding of a graph, and searching for a surface with uniform geometry on which that graph can be represented by a circle packing, several authors have studied a reversed version of this question: which uniform surfaces admit triangulated packings, circle packings for which each gap between circles is a circular horn triangle surrounded by three tangent circles? By the uniqueness part of the circle packing theorem, each packing is uniquely determined (up to symmetries of the surface) by its graph of tangencies, but for this problem, the graph of tangencies is determined from the geometry, rather than vice versa.

Among periodic infinite triangulated packings of the Euclidean plane, there is only one triangulated packing with a single radius, the hexagonal packing. There are nine distinct pairs of radii (normalized so the maximum radius is one), and 164 triples of radii, that form triangulated packings. In general, the number of ${\displaystyle k}$-tuples of radii that can form a triangulated packing is finite, but with an unknown growth rate as a function of ${\displaystyle k}$. The ratio of the smallest to largest radius is at most 0.701 for any triangulated packing other than the hexagonal packing, for which this ratio is 1. There is a packing with radius ratio approximately 0.651, with three distinct radii; it has been conjectured by Robert Connelly and Zhen Zhang to have the largest possible radius ratio of any non-hexagonal triangulated packing.

In 1986, Robert Brooks described a method of continuously associating a real number as an invariant of a circular rectangle, the region ${\displaystyle R}$ bounded by a cycle of four tangent circles (which may be given the symmetries of a rectangle by a Möbius transformation), in such a way that when the invariant is a rational number, the rectangle has a triangulated packing. His method first packs a chain of circles tangent to the top and bottom sides of ${\displaystyle R}$, with the leftmost circle in the chain tangent to the left side of ${\displaystyle R}$; let ${\displaystyle r_1}$ be the number of circles that can be packed in this way without overlapping the right side of ${\displaystyle R}$. This chain leaves a smaller circular rectangle between its rightmost circle and the right side of the starting rectangle; pack this rectangle recursively in the same way with another chain of circles, tangent to its left and right sides, and let ${\displaystyle r_2}$ be the number of circles in this second chain. This packing process may continue forever, giving an infinite sequence of positive integers ${\displaystyle r_i}$, the number of circles in each chain, or it may terminate after a finite number of stages with a triangulated packing. Regardless, Brooks defines his invariant ${\displaystyle r(R)}$ to be the simple continued fraction $${\displaystyle r(R)=r_1+\frac{1}{r_2+\frac{1}{r_3+\cdots }}.}$$ This is a rational number if and only if this packing process terminates with a finite triangulated packing.

Not every uniform surface admits a triangulated packing. For instance, in the case of flat tori (the quotient spaces of the Euclidean plane by a lattice, obtained by gluing opposite edges of a parallelogram), the geometry can vary continuously but, by the uniqueness of toroidal circle packings, only countably many distinct tori (up to scaling) have triangulated packings, and in particular they must have shapes that can be described by algebraic numbers. Nevertheless, Brooks showed that, for each possible genus of compact surfaces, the surfaces that have triangulated packings form a dense set in the Teichmuller space of all surfaces with that genus. This means that, for any given uniform compact surface, there exists another uniform compact surface, with almost the same geometry, on which there exists a triangulated packing. To prove this, Brooks first considers packings in which all gaps between triangles have either three or four sides, which can be obtained by placing circles to break up gaps with more sides into pieces with fewer sides. He then deforms each circular rectangle obtained in this way into a nearby rectangle whose invariant is rational to obtain a triangulated packing within each of the deformed rectangles. This produces a triangulation of the whole surface which, by the circle packing theorem, can be represented by a circle packing on a different uniform surface, slightly deformed from the given surface.

Applications

The circle packing theorem is a useful tool for problems including conformal maps, polyhedral realization of graphs, the planar separator theorem, graph drawing, random walks on planar graphs, and the visualization of the human brain.

Conformal mapping

A conformal map between two open sets in the plane or in a higher-dimensional space is a continuous function from one set to the other that preserves the angles between any two curves. The Riemann mapping theorem, formulated by Bernhard Riemann in 1851, states that, for any two open topological disks in the plane, there is a conformal map from one disk to the other. Conformal mappings have applications in mesh generation, map projection, and other areas. However, it is not always easy to construct a conformal mapping between two given domains in an explicit way.

A construction of William Thurston uses circle packings to approximate conformal mappings. More precisely, this construction maps an arbitrary open disk ${\displaystyle A}$ to the interior ${\displaystyle C}$ of a circle; the mapping from one topological disk ${\displaystyle A}$ to another disk ${\displaystyle B}$ could then be found by composing the map from ${\displaystyle A}$ to ${\displaystyle C}$ with the inverse of the map from ${\displaystyle B}$ to ${\displaystyle C}$. Thurston's idea was to pack circles of some small radius ${\displaystyle r}$ in a hexagonal tessellation of the plane, within region ${\displaystyle A}$, leaving a narrow region near the boundary of ${\displaystyle A}$, of width ${\displaystyle r}$, where no more circles of this radius can fit. He then constructs a maximal planar graph ${\displaystyle G}$ from the intersection graph of the circles, together with one additional vertex adjacent to all the circles on the boundary of the packing. By the circle packing theorem, this planar graph can be represented by a circle packing within circle ${\displaystyle C}$ in which all the edges (including the ones incident to the boundary vertex) are represented by tangencies of circles. The circles from the packing of ${\displaystyle A}$ correspond one-for-one with the circles within ${\displaystyle C}$, with the circle that forms the boundary of ${\displaystyle C}$ corresponding to the boundary of ${\displaystyle A}$.

This correspondence of circles can be used to construct a continuous function from ${\displaystyle A}$ to the interior of ${\displaystyle C}$ in which each circle and each gap between three circles is mapped from one packing to the other by a Möbius transformation. As ${\displaystyle n}$ goes to infinity, the function ${\displaystyle f_n}$ determined using Thurston's method from hexagonal packings of radius-${\displaystyle 1/n}$ circles converges uniformly on compact subsets of ${\displaystyle A}$ to a conformal map from ${\displaystyle A}$ to ${\displaystyle C}$. More generally, this holds for sequences of packings that are not necessarily hexagonal packings, as long as the sequence of maximum radii of the packings converges to zero. An alternative method hexagonally packs circles of small radius into ${\displaystyle C}$, and constructs a combinatorially equivalent packing of circles into ${\displaystyle A}$, tangent to its boundary; it converges in the same way. Practical applications of this method have been hindered by the difficulty of computing circle packings and by its relatively slow convergence rate. However, it has some advantages when applied to non-simply-connected domains and in selecting initial approximations for numerical techniques that compute Schwarz–Christoffel mappings, a different technique for conformal mapping of polygonal domains.

This construction of approximate conformal maps can also be described in terms of supplying a uniform geometry to a topological surface, and it can be extended from the surface itself to other objects embedded within the surface. An example comes from dessins d'enfant, a certain type of graph embedding used in algebraic geometry to study Riemann surfaces and the absolute Galois group. These automatically come with a triangulation, within which the dessin is a subset of the edges, but these triangulations may form multigraphs rather than simple graphs. By applying the circle packing theorem to subdivisions of these triangulations, an approximation of the dessin on a surface of uniform geometry may be constructed.

Quasiconformal mapping

When a conformal mapping is not possible, it may still be possible to obtain a quasiconformal mapping. Conformal mappings are smooth mappings from one Riemannian surface to another that, in the limit of small neighborhoods around any point, map circles to circles. Instead, quasiconformal mappings may, in the same limit, map circles to ellipses of bounded eccentricity, with smaller deformation as the bound on eccentricity approaches one. As one application of this idea, Monica Hurdal and Stephenson applied circle packing to the problem of constructing a flattened map of the functional regions of the human brain. To do this, they triangulate a three-dimensional model of the brain surface, find a circle packing representing the triangulation, and construct a piecewise-linear mapping from the triangles of the triangulated brain to the triangles of circle centers in the packing. They argue that this produces a quasiconformal mapping and therefore that it preserves the approximate shape of brain structures.

Brooks used this idea in a different way to study Kleinian groups, discrete subgroups of the symmetries of three-dimensional hyperbolic space. A Kleinian group is geometrically finite if it has a fundamental domain that is the intersection of finitely many half-spaces. Brooks shows that any geometrically finite group can be transformed by a quasiconformal mapping of arbitrarily small distortion into a subgroup of a Kleinian group with a fundamental domain of finite volume. If, moreover, the given Kleinian group has no cusps (either points at infinity where two bounding planes of the fundamental domain meet tangentially, or isolated points at infinity) it can be transformed by a quasiconformal mapping of arbitrarily small distortion into a subgroup of a Kleinian group with a compact fundamental domain, without points at infinity. The proof involves finding triangulated packings of surfaces whose geometry approximates the Riemann surfaces at the ends of the fundamental domain (the connected components of its points at infinity). The circles of these packings generate another Kleinian group, within which the circles coming from the boundaries of the fundamental domain generate a subgroup, close to the originally given group. G. Brock Williams used similar ideas to construct quasiconformal maps from a specified domain to the unit disk, having a specified distortion function.

Random walks

Several applications of the circle packing theorem use it to study random walks on planar graphs, based on the intuition that the approximation to conformal mapping of a circle packing can be used to relate these walks to Brownian motion, a geometric random process that is invariant under conformal maps. One result in this direction is that unbiased limit graphs of bounded-degree planar rooted graphs are almost surely recurrent, meaning that random walks on these graph limits almost surely return to the root infinitely often. The proof involves finding a circle packing that represents the limit graph, and using the ring lemma to bound the sizes of circles a small number of steps from the start of the walk, allowing the walk to be compared to a random walk on an integer grid. In 2000, Johan Jonnason working with Schramm used circle packings to prove that the expected cover time of a random walk on every ${\displaystyle n}$-vertex planar graph (the average number of steps of the walk before all vertices are visited) is ${\displaystyle \mathrm{\Omega }(n{\log }^{2}n)}$.

Instead of using methods from Brownian motion to understand random walks on graphs, circle packings can also be used to find graphs whose random walks approximate Brownian motion. For the same sequences of refined circle packings used to approximate conformal mappings of a domain, a random walk on the associated coin graph will reach a boundary vertex with a probability that approaches, in the limit as the circle packings become finer, the probability that a Brownian motion will reach a nearby point on the boundary of the domain.

Polyhedral realization and planar separators

The primal–dual packing of any polyhedral graph can be lifted from the plane to a sphere by stereographic projection. It can then be used to construct a convex polyhedron that has the given graph as its vertices and edges and that has a midsphere, a sphere tangent to all of the edges of the polyhedron. Each vertex of the polyhedron lies outside the sphere, at the apex of a cone that is tangent to the sphere along the circle corresponding to that vertex. This circle forms the horizon on the sphere, as viewed from the vertex. Each face of the polyhedron lies on the plane through its corresponding circle. Each edge of the polyhedron passes from one cone apex to another through the point of tangency of two circles, where both cones are tangent to the sphere. Conversely, if a polyhedron has a midsphere, then the circles formed by the intersections of the sphere with the polyhedron faces and the circles formed by the horizons on the sphere as viewed from each polyhedron vertex form a dual packing of this type.

Möbius transformations of the sphere lead to geometrically different polyhedron realizations. One particular realization, called the canonical polyhedron, is obtained by using a unit sphere and choosing a Möbius transformation that causes the center of the sphere to coincide with the centroid of the points of tangency of the polyhedron edges. All combinatorially equivalent polyhedra will produce in this way the same canonical polyhedron, up to rotations of the sphere. An alternative proof of the planar separator theorem, originally proved in a different way by Lipton and Tarjan, uses a similar idea of applying a Möbius transformation to a spherical circle packing. The construction obtains a circle packing on a sphere, representing the given graph. Next, a Möbius transformation of the sphere is used to transform a centerpoint of the circle centers, a point in space such that every plane through the centerpoint divides the ${\displaystyle n}$ centers into two subsets that each have size ${\displaystyle \le 3n/4}$, to coincide with the center of the sphere. A uniformly random plane through the center of the sphere intersects ${\displaystyle O(\sqrt{n})}$ of the circles of any packing of ${\displaystyle n}$ circles, in expectation. For the circle packing with the centerpoint at the sphere center, the vertices corresponding to these intersected circles form a separator that, when removed from the graph, leaves connected subgraphs of at most ${\displaystyle 3n/4}$ vertices. Circle packing has also been used to explain the success of spectral methods for constructing separators for graphs of bounded genus and bounded degree.

Graph drawing

Circle packing has been used as a frequent tool in graph drawing, the study of methods for visualizing graphs. Fáry's theorem, that every graph that can be drawn without crossings in the plane using curved edges can also be drawn without crossings using straight line segment edges, follows as a simple corollary of the circle packing theorem: by placing vertices at the centers of the circles and drawing straight edges between them, a straight-line planar embedding is obtained.

In 1994, Seth Malitz and Achilleas Papakostas applied circle packing to angular resolution, a measure of the quality of a graph drawing defined by the sharpest angle any two edges form at a shared vertex. They showed that planar graphs of bounded maximum degree have drawings of bounded angular resolution, using circle packing. They derived a version of the ring lemma and used it to prove that the angular resolution of the drawing in which each vertex is placed at the center of its circle is at least an inverse-exponential function of the degree. In 2013, Balázs Keszegh, János Pach, and Dömötör Pálvölgyi used a more complicated strategy for placing vertices, near the circle centers on subdivisions of integer lattices, in order to find drawings where the number of distinct edge slopes (the slope number) is at most an exponential function of the degree.

Primal–dual circle packings in the plane can be used to obtain simultaneous orthogonal drawings, straight-line planar drawings of any polyhedral graph and its dual graph, with one dual vertex at infinity, so that each primal and dual pair of edges cross at right angles. Such a drawing can be obtained from a primal–dual circle packing for which one dual circle surrounds the others, with all vertices (except the outer dual vertex) placed at the center of the corresponding circle. The use of circle packings to construct these drawings resolves a problem posed by W. T. Tutte in 1963. A pointed drawing of a given planar graph, in which the edges are drawn as smooth curves that, at each vertex, leave it in the same direction as each other, may be obtained by placing each vertex on the circle of a circle packing (rather than at its center) and drawing each edge as a biarc formed by two circular arcs, perpendicular to the circles of the packing, through the point of tangency of two circles. Circle packings have also been used to obtain strongly monotone drawings of polyhedral graphs. These are straight-line drawings in which every two vertices are connected by a polygonal path that is monotone with respect to the line segment between the two vertices (its orthogonal projection onto this line segment is one-to-one). Another construction involving circle packing produces a Lombardi drawing for any subcubic planar graph, a drawing resembling a two-dimensional soap bubble foam in which the edges are drawn as circular arcs that meet at equal angles at each vertex.

Algorithmic aspects

When a circle packing exists, it exists with algebraic numbers for its center and radii, solving a system of quadratic equations that represent the requirements that each two centers of tangent circles be at a distance from each other equal to the sum of their radii. Therefore, in principle, it is possible to find circle packings using methods from symbolic computation for solving systems of polynomial equations, such as the Gröbner basis method. However, this approach can require the solution of high-degree polynomial equations, with unsolvable Galois groups. Instead, researchers have focused on more efficient numerical methods for finding accurate approximations to the centers and radii of circle packings.

One of the earliest and most versatile of these approximation results, announced by Bojan Mohar in 1993 with details in two subsequent papers, can be used to find primal–dual circle packings on surfaces of arbitrary genus, in time polynomial in the number of circles and in the number of bits of precision used to specify the output to the desired accuracy. Mohar's algorithm is an iterative method applied to the system of radii of a primal–dual circle packing, starting from an initial inaccurate system of radii. It considers the orthodiagonal quadrilaterals formed by each pair of crossing primal and dual edges. From a system of radii, one can calculate the angles of these quadrilaterals (if the circles could be packed with these radii): for a system of radii to form a packing, these angles should sum to ${\displaystyle 2\pi }$ around each vertex. For systems of radii that do not give the correct sums, Mohar partitions the radii into a subset of radii that are too large (the angles around that vertex sum to less than ${\displaystyle 2\pi }$ and a complementary subset of radii that are too small, and uses the bisection method to find two parameters ${\displaystyle \beta }$ and ${\displaystyle \gamma }$ such that multiplying the large radii by ${\displaystyle \beta }$ and the small radii by ${\displaystyle \gamma }$ reduces the mean squared error between the angle sums and ${\displaystyle 2\pi }$. After a sufficient number of repetitions of this process, it leads to an accurate system of radii. Mohar uses these radii to place the circle centers, starting from one primal–dual quadrilateral and then using the already placed centers of each quadrilateral and the radii of its circles to determine the locations of the remaining centers. Although Mohar states that the algorithm runs in polynomial time, he does not state its polynomial time bound explicitly. A later study suggested that the computational complexity of Mohar's packing algorithm is at least quintic in the number of circles to be packed.

A simpler iterative method that modifies only one circle radius at a time was provided by Charles Collins and Kenneth Stephenson, again computing the system of circle radii before using the radii to place the circle centers. The version of the circle packing problem that they solve produces a circle packing in the Euclidean plane for a maximal planar graph, with a specified outer triangle and with specified radii for the three circles of this triangle. They begin with a set of tentative radii that do not correspond to a valid packing, and then repeatedly perform the following steps:

1. Choose an internal vertex ${\displaystyle v}$ of the input graph.
2. Calculate the total angle ${\displaystyle \theta }$ that its ${\displaystyle k}$ neighboring circles would cover around the circle for ${\displaystyle v}$, if the neighbors were placed tangent to each other and to the central circle using their tentative radii.
3. Determine a representative radius ${\displaystyle r}$ for the neighboring circles, such that ${\displaystyle k}$ circles of radius ${\displaystyle r}$ would give the same covering angle ${\displaystyle \theta }$ as the neighbors of ${\displaystyle v}$ give.
4. Set the new radius for ${\displaystyle v}$ to be the value for which ${\displaystyle k}$ circles of radius ${\displaystyle r}$ would give a covering angle of exactly ${\displaystyle 2\pi }$.

Each of these steps may be performed with simple trigonometric calculations. Collins and Stephenson prove that, applied only to a single vertex, this method rapidly converges to a radius that gives covering angle ${\displaystyle 2\pi }$. Further, they argue that the system also globally converges to a consistent system of radii, and they provide computational experiments suggesting that the rapid local convergence of this method extends to rapid global convergence of the entire system of radii. Once the system has converged, the circles may be placed one at a time, similarly to the algorithm of Mohar, at each step using the positions and radii of two neighboring circles to determine the center of each successive circle.

Another algorithm by Gerald L. Orick, Stephenson, and Collins in 2017 applied to the same planar packings as the original work by Collins and Stephenson in 2003 and approximates both the system of radii and circle centers simultaneously and iteratively. It alternates between steps that use a weighted Tutte embedding to place the centers, and that use the resulting circle centers to determine improved radii. Although they provide no theoretical guarantees on the performance of this algorithm, Orick et al. claim that their experiments show linear convergence to a consistent packing in practice, which, when true, would lead to a polynomial time bound.

The case of finding planar packings for maximal planar graphs was revisited in 2020 by Lee Sally, Yin Lee, and Kent Quanrud, but they used an explicit time bound. Although focused only on a primal circle packing, they work with the system of radii of a primal–dual packing, for maximal planar graphs only, with a dual circle for each triangular face of the graph. Like Mohar, they use orthodiagonal quadrilaterals determined by crossing pairs of primal and dual edges, with angles calculated from a given system of radii, which for a valid system of radii should sum to ${\displaystyle 2\pi }$ at each vertex. Following the 1991 work by Colin de Verdière, they set up a convex optimization problem in which the variables to be optimized are the logarithms of the radii of the primal–dual packing, and the convex function to be minimized combines terms that are linear in these variables and in the antiderivatives of the arctangents of ratios of radii. They show that the minimizer of this function provides a system of radii that meet the conditions of a circle packing in that the angles of the quadrilaterals around each vertex sum to ${\displaystyle 2\pi }$. By finding a spanning tree of the graph of orthogonal circles in the packing with the property that each spanning tree edge connects circles whose radii are not too far from each other, they prove that this function is strongly convex near its minimum, allowing the application of powerful methods from convex programming. Based on these techniques, they give a time bound for finding a packing of $${\displaystyle \tilde{O}\left(n\log \frac{R}{\epsilon }\right),}$$ where the ${\displaystyle \tilde{O}}$ is a form of big O notation that suppresses terms that are logarithmic in its argument, ${\displaystyle n}$ is the number of circles to be packed, ${\displaystyle R}$ is the ratio between the largest and smallest radius in the resulting packing (which may be at worst exponential in ${\displaystyle n}$), and ${\displaystyle \epsilon }$ is a parameter that controls how accurate the numerical approximation to the packing should be. All computed radii are within a ${\displaystyle 1+\epsilon }$ factor of the radius of an exact circle packing, and all computed centers are at a distance from the centers of an exact circle packing that is at most ${\displaystyle \epsilon }$ times the radius of the smallest circle.

The concept of circle packings is used in load‑balanced position-based routing based applications. A group of computer scientists in which Jie Gao was part of developed an approach that uses a numerical distributed algorithm, based on a discrete Ricci flow, to construct approximate primal–dual circle packings on a sphere, from which midsphere polyhedra are derived. These polyhedra support a scheme developed by computer scientists Christos Papadimitriou and David Ratajczak where messages can be forwarded from vertex to a neighboring vertex of this polyhedron in a way that always increases the inner product of the three-dimensional coordinates of the current location and destination. The existence of a midsphere guarantees that the message eventually reaches its destination.

History

Stephenson writes that "there is indeed a long tradition behind our story", and attributes the familiar hexagonal packing of congruent circles to folklore. Other early works on circle packings with specific patterns of tangency include:

• Descartes' theorem on the radii of four mutually tangent circles, stated by René Descartes in 1643 and by Japanese mathematician Yamaji Nushizumi in 1751.
• A variant of the Apollonian gasket, an infinite fractal circle packing formed by repeatedly placing a circle within each circular triangle between larger circles in the packing, is mentioned in a 1706 letter by Leibniz.
• The 1910 work of Arnold Emch on Doyle spirals in the mathematics of plant growth (phyllotaxis).

The circle packing theorem itself was first stated and proved by Koebe in 1936. Thurston mentioned results on the circle packing theorem in a 1978 talk at the International Congress of Mathematicians, and noted that it followed from the work of E. M. Andreev. In the same year, Gerd Wegner also conjectured that the circle packing theorem holds. At the Bieberbach conference in 1985, Thurston proposed a scheme for using the circle packing theorem to obtain a homeomorphism of a simply connected proper subset of the plane onto the interior of the unit disk, and he conjectured that this scheme converges to the Riemann mapping as the radii of the circles tend to zero. Thurston's conjecture was proven in 1987 by Burton Rodin and Dennis Sullivan. Thurston's work in this area brought the topic of circle packings to the attention of mathematicians and led to the formation of a research community centered on this idea.