6
$\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.

$\endgroup$
  • 2
    $\begingroup$ A proof can be found in Stephenson's lovely book "Introduction to Circle Packing: The Theory of Discrete Analytic Functions". $\endgroup$ – Andy Putman Nov 22 '14 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 Nov 23 '14 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 Nov 23 '14 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 Nov 23 '14 at 2:35
  • 2
    $\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 Nov 23 '14 at 9:09
10
$\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.
$\endgroup$
  • 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 Nov 23 '14 at 19:06
  • 1
    $\begingroup$ Also, what is Andre'ev, chopped liver? Geez, talk about revisionism... $\endgroup$ – Igor Rivin Nov 23 '14 at 19:08
  • $\begingroup$ @IgorRivin. Sorry, just revised the list. Which of Andreev's should I put? $\endgroup$ – Hao Chen Nov 23 '14 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 Nov 23 '14 at 20:18
7
$\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.

$\endgroup$
  • $\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 Feb 16 '15 at 1:07
  • $\begingroup$ @NeilHoffman: Ok, I fixed the reference - no secret chapter 16 that I know of. $\endgroup$ – Ian Agol Feb 16 '15 at 4:05
6
$\begingroup$

EDIT. There are very many published proofs. For example, Colin de Verdiere (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 Verdiere (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.

$\endgroup$
  • $\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 Nov 23 '14 at 19:09
  • $\begingroup$ You are right. I will edit. $\endgroup$ – Alexandre Eremenko Nov 23 '14 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.