12
$\begingroup$

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!

Improve this question
$\endgroup$
3
  • $\begingroup$ I do not see how to put the complete graph on 6 vertices, $K_6,$ in $\mathbb R^3.$ A regular tetrahedron with an extra point in the center gives $K_5.$ $\endgroup$
    – Will Jagy
    Commented Jan 13, 2012 at 4:05
  • $\begingroup$ there also seems to be a related square tiling $\endgroup$
    – john mangual
    Commented Jan 13, 2012 at 4:10
  • $\begingroup$ It is a little uncertain, but the articles about recognizing ball-touching graphs appear to restrict to unit radius... citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.672 $\endgroup$
    – Will Jagy
    Commented Jan 13, 2012 at 5:53

5 Answers 5

Reset to default
7
$\begingroup$

Yes, certain restrictions are well known. One reference is Kuperberg & Schramm here ("Average kissing numbers for non-congruent sphere packings", 1994) which says that such graphs would have to have average degree <15. A more recent reference is Benjamini & Schramm here ("Lack of Sphere Packing of Graphs via Non-Linear Potential Theory", 2009) which shows that certain low degree infinite graphs are not realizable this way.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Also, $K_6$ cannot be a subgraph, from Ian's answer. $\endgroup$
    – Will Jagy
    Commented Jan 13, 2012 at 6:12
  • 1
    $\begingroup$ Yeah, this is Exc. 20.12 (and a solution at the end) in my book math.ucla.edu/~pak/geompol8.pdf $\endgroup$
    – Igor Pak
    Commented Jan 13, 2012 at 6:28
  • $\begingroup$ I see, part (c) , page 191, answer page 395, exactly what Ian came up with. Do you think we can always place a graph with $n$ vertices in $\mathbb R^{n-2}?$ $\endgroup$
    – Will Jagy
    Commented Jan 13, 2012 at 7:00
  • $\begingroup$ Well, by Ian's argument, you can send two spheres to tangent hyperplanes, at which point you are asking if you can place a $K_{n-2}$ in $\mathbb{R}^{n-3},$ which you can, by the magic of regular simplices. $\endgroup$
    – Igor Rivin
    Commented Jan 13, 2012 at 9:21
  • $\begingroup$ Igor, this seems to be the induction step in your book's answer. I am still uncertain about graphs on $n$ vertices that are not complete, in $\mathbb R^{n-1}$ or possibly $R^{n-2}.$ Steve Carnahan feels that there is enough room in $\mathbb R^{n-1}$ to slightly perturb the positions of the balls (so as to erase edges from a complete graph and realize the graph we are actually given), perhaps keeping all radii the same. Note that we can do all graphs with 5 vertices in $\mathbb R^3,$ if not complete then planar, if complete then a regular tetrahedron with a smaller ball at center. $\endgroup$
    – Will Jagy
    Commented Jan 13, 2012 at 20:11
13
$\begingroup$

I don't know of any results on this. There are some reformulations in terms of Gram matrices, but I don't know if they help.

For $K_6$, there is no realization by touching spheres. Suppose you had such a realization. The property of having tangent spheres realizing a graph is invariant under Mobius transformations. In particular, one may perform a Mobius transformation sending the tangency between two spheres to infinity in $\mathbb{R}^3$. The two spheres are sent to parallel planes, and the other 4 spheres are tangent to both of these planes and to each other. In particular, the midplane between these two planes intersects the other 4 spheres in 4 tangent circles of equal radius. But 4 equal radius circles in the plane cannot be simultaneously tangent. So $K_6$ cannot be realized by tangent spheres.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Looks like according to Pak this was discovered by Benjamini in 2010. $\endgroup$
    – Ian Agol
    Commented Jan 13, 2012 at 15:58
8
$\begingroup$

According to corollary 4.6 of "Representing Graphs by Disks and Balls (a survey of recognition-complexity results)" these graphs are NP hard to recognize.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ This is clearly THE answer, interesting though @Igor Pak's is. $\endgroup$
    – Igor Rivin
    Commented Jan 13, 2012 at 12:42
  • $\begingroup$ Here's more of the reference: Hliněný and Kratochvı́l, Discrete Mathematics 229: 101–124 (2001). The paper is available online here sciencedirect.com/science/article/pii/S0012365X00002041 $\endgroup$
    – j.c.
    Commented Apr 5, 2016 at 16:39
3
$\begingroup$

I can make a pretty good case for sphere packing of a finite graph in some $\mathbb R^n.$ From http://en.wikipedia.org/wiki/Circle_packing_theorem#Generalizations_of_the_circle_packing_theorem we learn that a nonplanar graph still induces a circle packing on a compact orientable surface of larger genus, the surface having constant curvature. For example, for planar graphs we could realize them either as circle packings in the plane, then simply make those into spheres (thereby done), or we could make a circle packing on $\mathbb S^2$ and then ask whether we can blow up those circles into spheres with the same tangency relationships. The answer is yes, for each circle, take the sphere that intersects $\mathbb S^2$ orthogonally in precisely that circle.

For torus graphs, I am betting on 3-spheres in $\mathbb R^4,$ where we can take the flat Clifford torus. For larger genus, from Nash embedding we can take our compact surface with constant curvature $-1$ in some $\mathbb R^n.$

Well, somebody just posted an answer, it says so at the top of the page, maybe they actually know something.

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 Riemannian 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.

EDIT: I suspect it is worth trying to disprove $\mathbb R^3$ for, say, $K_7,$ which is a torus graph. See Topological Graph Theory by Jonathan L. Gross and Thomas W. Tucker. If $K_7$ works in $\mathbb R^3$ try $K_8$ and $K_9,$ the dog graph.

EDIT TOO: some anecdotal evidence, we can always place $K_n$ as the regular simplex in $\mathbb R^{n-1}.$ So now it is a question of how to selectively erase edges in order to get the graph we are actually given...Note that the articles on ball-touching in $\mathbb R^3$ all seem to be about balls of fixed unit radius.

Improve this answer
$\endgroup$
2
  • $\begingroup$ In $\mathb{R}^{n-1}$, you have enough room to suitably perturb the simplex by some small $\epsilon$ without changing the sizes of the discs. If I'm not mistaken, you may also surround such a formation of discs with a $n+1$st disc turned inside-out (i.e., you can get a valid formation by a Möbius transformation). $\endgroup$
    – S. Carnahan ♦
    Commented Jan 13, 2012 at 7:34
  • $\begingroup$ @S. Carnahan Thanks, I asked Igor the same thing, or tried to, I don't see that his argument applies to any possible incomplete graph on $n$ vertices. I think he was just showing me the induction step in the answer in his book, which is about the complete graphs. $\endgroup$
    – Will Jagy
    Commented Jan 13, 2012 at 19:30
2
$\begingroup$

These are ball-touching graphs; according to some google sources they seem to be NP hard to recognize.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

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