Combinatorics – Proof of Koebe–Andreev–Thurston Theorem

co.combinatoricsgraph theoryplane-geometryreference-request

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.

Best Answer

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.
Related Question