13
$\begingroup$

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two discs are tangent iff the corresponding vertices are connected to each other.

Where can I find the/a proof of this theorem, and what should I learn to understand it?

I prefer proofs which are elementary, but other proofs are welcome too.

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ A proof can be found in Stephenson's lovely book "Introduction to Circle Packing: The Theory of Discrete Analytic Functions". $\endgroup$
    – Andy Putman
    Commented Nov 22, 2014 at 22:11
  • $\begingroup$ I'm confused. I knew of these as "coin graphs", and thought it was open whether every planar graph was coin: jstor.org.proxy.library.cornell.edu/stable/2324291 but the theorem seems to be older than the book reviewed. $\endgroup$
    – Allen Knutson
    Commented Nov 23, 2014 at 0:57
  • $\begingroup$ @AllenKnutson: I'm not familiar with the term "coin graphs", but the circle packing theorem as stated in the question is quite old (it basically goes back to Koebe, though it has been rediscovered several times). My guess is that this is simply a matter of two communities of people not talking to each other. The various proofs of the circle packing theorem that I know are not really combinatorial. As Thurston taught us, constructing a circle packing is very similar to constructing a conformal map, so it does not surprise me that the graph theory community has not managed to prove it. $\endgroup$
    – Andy Putman
    Commented Nov 23, 2014 at 2:33
  • $\begingroup$ nb: As an illustration of the connection to conformal geometry, you can construct circle packing of the disc from any planar graph; the "exterior" circles are all tangent to the exterior circle. The different possible unit disc circle packings realizing a given planar graph then differ by Mobius transformations. $\endgroup$
    – Andy Putman
    Commented Nov 23, 2014 at 2:35
  • 3
    $\begingroup$ At least some sources define coin graphs as graphs induced by a "coin" of a fixed radius, i.e. graphs defined by discs as in the circle packing theorem, but with all discs congruent. I believe this may be the open problem referred to, and I think the circle packing theorem is widely known in graph theory. See for example these notes from a workshop: buet.ac.bd/cse/HEQEP/upload_path/FIles/Brainstorming_Workshops/…. The review above is also not entirely clear about the definition. $\endgroup$
    – Sasho Nikolov
    Commented Nov 23, 2014 at 9:09

3 Answers 3

Reset to default
17
$\begingroup$

There are many proofs, and I'm not claiming that the following list is complete. New references are welcome.

(First proof)

  • Paul Koebe, Kontaktprobleme der konformen Abbildung, Ber. Verh. Sächs. Akad. Leipzig 88 (1936), 141–164 (German)

(Thurston's rediscovery and related)

  • Andreev, E. M., Convex polyhedra of finite volume in Lobačevskiĭ space, Mat. Sb. (N.S.) 83 (1970), no. 125, 256–260.
  • (see also) Roeder, Roland K.W., Hubbard, John H. and Dunbar, William D., Andreev’s Theorem on hyperbolic polyhedra, Annales de l’institut Fourier 57 (2007), no. 3, 825–882.
  • William P. Thurston and John W. Milnor, The Geometry and Topology of Three-Manifolds

(Variational principle)

  • Yves Colin de Verdière, Un principe variationnel pour les empilements de cercles, Invent. Math. 104 (1991), no. 3, 655–669 (French).
  • Igor Rivin, Euclidean structures on simplicial surfaces and hyperbolic volume, Ann. of Math. 139 (1994), 553–580.
  • Alexander I. Bobenko and Boris A. Springborn, Variational principles for circle patterns and Koebe’s theorem, Trans. Amer. Math. Soc. 356 (2004), no. 2, 659–689.
  • (see also) Günter M. Ziegler, Convex polytopes: extremal constructions and f-vector shapes, Geometric Combinatorics, 2007, pp. 617–691.

(An inductive proof ?)

  • Kenneth Stephenson, Introduction to Circle Packing: The theory of discrete analytic functions, Cambridge University Press, Cambridge, 2005.

(I also recommend the following completion of the theorem)

  • Graham R. Brightwell and Edward R. Scheinerman, Representations of planar graphs, SIAM J. Discrete Math. 6 (1993), no. 2, 214–229.
Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Bobenko and Springborn??? That argument is due to yours truly (annals, 1994), B&S give a dual version, which connects my argument with Colin de Verdiere's. $\endgroup$
    – Igor Rivin
    Commented Nov 23, 2014 at 19:06
  • 2
    $\begingroup$ Also, what is Andre'ev, chopped liver? Geez, talk about revisionism... $\endgroup$
    – Igor Rivin
    Commented Nov 23, 2014 at 19:08
  • 3
    $\begingroup$ @IgorRivin. Sorry, just revised the list. Which of Andreev's should I put? $\endgroup$
    – Hao Chen
    Commented Nov 23, 2014 at 19:28
  • $\begingroup$ Andreev's second paper (on polyhedra of finite volume, but also the Roeder/Hubbard fix to the error in Andreev's paper). $\endgroup$
    – Igor Rivin
    Commented Nov 23, 2014 at 20:18
9
$\begingroup$

This is proved in sections 13.6 and 13.7 of Thurston's notes. See also Corollary 5.10.4 and section 5.11 of Thurston's book. Another short proof appears in Appendix 2 of Rodin and Sullivan.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There might be a typo here. The relevant sections for Andre'ev's Theorem and circle packings are 13.6 and 13.7. However, if there is a secret chapter 16 of Thurston's notes, I would love to know about it! $\endgroup$
    – Neil Hoffman
    Commented Feb 16, 2015 at 1:07
  • $\begingroup$ @NeilHoffman: Ok, I fixed the reference - no secret chapter 16 that I know of. $\endgroup$
    – Ian Agol
    Commented Feb 16, 2015 at 4:05
7
$\begingroup$

EDIT. There are very many published proofs. For example, Colin de Verdière (Forum Math., 1 (1989) 395-402), or Charles R. Collins and Kenneth Stephenson, A circle packing algorithm, Computational Geometry 25 (2003) 233–256.

Thurston's original proof is elementary: he gives an algorithm for finding the (essentially unique) circle packing from a triangulation. He never published this properly; his "Geometry and Topology of 3-manifolds" exists as a preprint, and the proof there are sketchy. Then Colin de Verdière (Forum Math., 1 (1989) 395-402) proved accurately convergence of Thurston's algorithm. Another proof of convergence and implementation on computer is in the paper of Collins and Stephenson mentioned above. Then there were many generalizations and versions of this theorem and algorithm, too many to list all of them here.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Rodin and Sullivan proved that circle packing maps converge to the Riemann mapping, NOT the circle packing theorem. The convergence of Thurston's algorithm was proved by Marden and Rodin, though Thurston's original observation (that circle packing follows from Andre'ev's theorem) is a two-line remark (but does not apply to higher genus). $\endgroup$
    – Igor Rivin
    Commented Nov 23, 2014 at 19:09
  • $\begingroup$ You are right. I will edit. $\endgroup$
    – Alexandre Eremenko
    Commented Nov 23, 2014 at 21:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .