Circle packing theorem

From Wikipedia, the free encyclopedia

The circle packing theorem (also known as the Koebe-Andreev-Thurston theorem) describes the possible tangency relations between circles in the plane whose interiors are disjoint. A packing of circles is a collection of circles whose interiors are disjoint. The intersection graph (or contact graph) of the packing is a graph whose vertex set is in bijection with the set of circles, and two vertices are connected by an edge if and only if the corresponding circles touch. The intersection graph of a circle packing in the plane is always a planar graph, since we may take the center of every circle to be the corresponding vertex, connect centers of touching circles by a straight line segment, resulting in a planar embedding of the intersection graph. The circle packing theorem states that the converse also holds:

Circle packing theorem: For every planar graph G there is a circle packing in the plane whose intersection graph is isomorphic to G.

Contents

[edit] Examples

 Please help improve this section by expanding it.
Further information might be found on the talk page or at requests for expansion.


[edit] A uniqueness statement

A finite graph G is a triangulation of the sphere, if it is embedded in the sphere and every connected component of the complement of G has precisely three edges on its boundary. If G is a triangulation of the sphere, then the corresponding circle packing is unique, up to Möbius transformations and reflections in lines.

Thurston[1] observes that this uniqueness is a consequence of the Mostow rigidity theorem. The plane in which the circles are packed may be viewed as the boundary of a halfspace model for hyperbolic space; with this view, each circle is the boundary of a plane within the hyperbolic space. One can define a set of disjoint planes from the circles of the packing, and a second set of disjoint planes defined by the circles surrounding each triangular gap between three of the circles in the packing. These two sets of planes meet at right angles, and form the generators of a reflection group whose fundamental domain can be viewed as a hyperbolic manifold. By Mostow rigidity, the hyperbolic structure of this domain is uniquely determined, up to isometry of the hyperbolic space; these isometries, when viewed in terms of their actions on the Euclidean plane on the boundary of the half-plane model, translate to Möbius transformations.

There is also a more elementary proof based on the maximum principle, which we now sketch. The key observation here is that if you look at the triangle formed by connecting the centers of three mutually tangent circles, then 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. Consider two packings corresponding to G. First apply reflections and Möbius transformations to make the outer circles in these two packings correspond to each other and have the same radii. Next, consider a vertex v where the ratio between the corresponding radius in the one packing and the corresponding radius in the other packing is maximized. Since the angles formed at the center of the corresponding circles are the same, it follows from the above observation that the radius ratio is the same at all the neighbors of v as well. Since G is connected, we conclude the radii in the two packings are the same, which proves uniqueness.

[edit] Generalizations of the circle packing theorem

The circle packing theorem generalizes to graphs that are not planar. If G is a graph that can be embedded on a surface S, then there is a constant curvature Riemannnian metric d on S and a circle packing on (S,d) whose contacts graph is isomorphic to G. If S is closed (compact and without boundary) and G is a triangulation of S, then (S,d) and the packing are unique up to conformal equivalence. If S is the sphere, then this equivalence is up to Möbius transformations; if it is a torus, then the equivalence is up to scaling by a constant and isometries, while if S has genus at least 2, then the equivalence is up to isometries.

Another generalization of the circle packing theorem involves replacing the condition of tangency with a specified intersection angle between circles corresponding to neighboring vertices. A particularly elegant version is as follows. Suppose that G is a finite 3-connected planar graph, then there is a pair of circle packings, one whose intersection graph is isomorphic to G, another whose intersection graph is isomorphic to the planar dual of G, and for every vertex in G and face adjacent to it, the circle in the first packing corresponding to the vertex intersects orthogonally with the circle in the second packing corresponding to the face[2].

Yet another variety of generalizations allow shapes that are not circles. Suppose that G = (V,E) is a finite planar graph, and to each vertex v of G corresponds a shape K_v\subset\mathbb R^2, which is homeomorphic to the closed unit disk and whose boundary is smooth. Then there is a packing P = (K'_v:v\in V) in the plane such that K'_v\cap K'_u\ne \emptyset if and only if [v,u]\in E and for each v\in V the set K'v is obtained from Kv by translating and scaling. (Note that in the original circle packing theorem, there are three real parameters per vertex, two of which describe the center of the corresponding circle and one of which describe the radius, and there is one equation per edge. This also holds in this generalization.) One proof of this generalization can be obtained by applying Koebe's original proof[3] and the theorem of Brandt[4] and Harrington[5] stating that any finitely connected domain is conformally equivalent to a planar domain whose boundary components have specified shapes, up to translations and scaling.

[edit] Relations with conformal mapping theory

Circle packings can be used to approximate conformal mappings between specified domains. Each circle on the left corrsponds to a circle on the right.
Circle packings can be used to approximate conformal mappings between specified domains. Each circle on the left corrsponds to a circle on the right.
 Please help improve this section by expanding it.
Further information might be found on the talk page or at requests for expansion.


[edit] Applications of the circle packing theorem

The circle packing theorem is a useful tool to study various problems in planar geometry, conformal mappings and planar graphs. An elegant proof of the Lipton-Tarjan theorem about separators in planar graphs has been obtained in this way[6]. Another application of the circle packing theorem is that unbiased limits of bounded degree planar graphs are almost surely recurrent[7]. Other applications include implications for the cover time[8]. and estimates for the largest eigenvalue of bounded genus graphs [9].

[edit] Proofs of the theorem

There are many known proofs of the circle packing theorem. Paul Koebe's original proof is based on his conformal uniformization theorem saying that a finitely connected planar domain is conformally equivalent to a circle domain. There are several different topological proofs that are known. Thurston's proof is based on Brouwer's fixed point theorem. There is also a proof using a discrete variant of Perron's method of constructing solutions to the Dirichlet problem. Yves Colin de Verdière proved[10] the existence of the circle packing as a minimizer of a convex function on a certain configuration space.

 Please help improve this section by expanding it.
Further information might be found on the talk page or at requests for expansion.


[edit] Algorithmic aspects

William Thurston invented and implemented an algorithm for calculating a circle packing corresponding to a given planar graph, based on repeated local relaxations. A program by Kenneth Stephenson implementing a variant of this algorithm is available. Some variant of the algorithm has been proved to converge in polynomial time[11].

[edit] History

The circle packing theorem was first proved by Paul Koebe[3]. William Thurston[1] rediscovered the circle packing theorem, and noted that it followed from the work of E. M. Andreev. Thurson also proposed a scheme by which circle packings can be used to approximate the Riemann mapping between a simply connected open connected proper subset in the plane and the unit circle. This was later proved by Burton Rodin and Dennis Sullivan[12]. This led to a flurry of research on extensions of the circle packing theorem, relations to conformal mappings, and applications.

[edit] See also

[edit] Notes

  1. ^ a b Thurston, Chap. 13
  2. ^ Brightwell and Scheinerman (1993)
  3. ^ a b Koebe (1936)
  4. ^ Brandt (1980)
  5. ^ Harrington (1982)
  6. ^ Miller and Thurston (1990)
  7. ^ Benjamini and Schramm (2001)
  8. ^ Jonnason and Schramm (2000)
  9. ^ Kelner (2006)
  10. ^ Colin de Verdière (1991)
  11. ^ Mohar (1993)
  12. ^ Rodin and Sullivan (1987)

[edit] References

  • I. Benjamini and O. Schramm, Recurrence of distributional limits of finite planar graphs, Electron. J. Probab. 6 (2001).
  • M. Brandt, Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete, Bull. de la Soc. des Sc. et des Lettr. de Łódź, 30 (1980).
  • G. R. Brightwell and E. R. Scheinerman, Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), 214-229.
  • Y. Colin de Verdière, Une principe variationnel pour les empilements de cercles, Inventiones Mathematicae, 104 (1991), 655-669.
  • A. Harrington, Conformal mappings onto domains with arbitrarily specified boundary shapes, J. Analyse Math. 41 (1982), 39-53.
  • J. Jonnason and O. Schramm, On the cover time of planar graphs, Electron. Comm. Probab. 5 (2000), 85-90.
  • J. Kelner, Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus, SIAM J. Comput. 35 (2006), 882-902.
  • P. Koebe, Kontaktprobleme der Konformen Abbildung, Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88 (1936), 141--164.
  • G. L. Miller and W. P. Thurston, Separators in two and three dimensions, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, (1990), 300-309.
  • B. Mohar, A polynomial time circle packing algorithm, Discrete Math., 117 (1993), 257-263.
  • B. Rodin and D. Sullivan, The convergence of circle packings to the Riemann mapping, J. Differential Geometry, 26 (1987), 349-360.
  • K. Stephenson, Introduction to circle packing, the theory of discrete analytic functions, Cambridge University Press, Cambridge, 2005.
  • W. P. Thurston, The finite {Riemann} mapping theorem, invited talk, An International Symposium at Purdue University on the occasion of the proof of the Bieberbach conjecture, (1985).
  • William Thurston, The geometry and topology of 3-manifolds, Princeton lecture notes (1978-1981).