Skip to main content
5 of 5
broken image fixed (click 'rendered output' or 'side-by-side' to see the difference; image retrieved via Wayback Machine); for more info, see https://meta.mathoverflow.net/a/4058/70594

Extensions of the Koebe–Andreev–Thurston theorem to sphere packing?

The Koebe–Andreev–Thurston theorem states that any planar graph can be represented "in such a way that its vertices correspond to disjoint disks, which touch if and only if the corresponding vertices are adjacent" (to quote Günter Ziegler, Lectures on Polytopes, Springer, 1995 p.117. (See also the Wikipedia article, "Circle packing theorem.")
          Circle Packing
(source: uci.edu)

(Image due to David Eppstein, here.)

What is the corresponding statement for spheres in $\mathbb{R}^3$? Every graph $G$ satisfying property $X$(?) can be represented by touching spheres.

This is surely known—Thanks for pointers!

Joseph O'Rourke
  • 150.9k
  • 36
  • 358
  • 958