Minimum dimension for sphere packing a graph in Euclidean space

Question

Igor Pak suggested I ask this as a separate question. In Extensions of the Koebe–Andreev–Thurston theorem to sphere packing? it was asked whether there were simple conditions to decide whether a finite graph could be expressed by a bunch of spheres in $\mathbb R^3,$ two spheres touching if and only if the relevant vertices shared an edge.

Scott Carnahan and I are of the opinion that any graph on $n$ vertices can be placed in $\mathbb R^{n-1}$ in the manner described. It is proved in Igor's book that the complete graph can be placed in $\mathbb R^{n-2}$ and no smaller dimension, one regular simplex with unit radii and then one extra sphere in the center. Of course, the complete graph can also be placed as a regular simplex with all unit spheres in $\mathbb R^{n-1}.$ But the varying radius question seems more fortunate, we get the same answer, if it works, in $\mathbb H^{n-1}$ and $\mathbb S^{n-1}.$

So, that is the initial question, can anyone prove that any graph on $n$ vertices, however many or few edges, can be placed in $\mathbb R^{n-1}$ as a set of spheres, if we allow varying radius?

Secondarily, and I have not the slightest idea, is there any sort of expected value of the minimum dimension, or, at least, some sort of "normal behavior" for this, meaning that "most" graphs on $n$ vertices need a minimum dimension of about ____?

Answer 1

Start with a regular simplex with unit length edges in ${\mathbf{R}}^{n-1}$, representing $K_n$. In any non-degenerate simplex, one can increase or decrease the length of any edge by a sufficiently small amount, leaving all other edge lengths fixed and flexing the dihedral angle opposite to the edge. Do this to increase the length of every edge in $K_n$ that is not present in your given graph $G$, one edge at a time. Finally, place radius-1/2 balls at the vertices of the resulting simplex. The result is a sphere packing representing $G$.

Answer 2

This is a longish comment rather than a complete answer.

Long ago Fred Roberts introduced the notion of the "boxicity" of a graph, and later the related notion of "sphericity" of a graph was studied. To quote Michael and Quint in their paper, "Sphericity, cubicity, and edge clique covers of graphs," Discrete Applied Mathematics, Volume 154, Issue 8, 2006,

The sphericity sph$(G)$ of a graph $G$ is the minimum dimension $d$ for which $G$ is the intersection graph of a family of congruent spheres in $\mathbb{R}^d$.

There are upper bounds known on the sphericity of graphs. The paper I quoted shows that sph$(G) \le \theta(G)$, where $\theta(G)$ is the edge clique cover number of $G$, i.e., "the minimum cardinality of a set of cliques that covers all edges of $G$."

Here's another upper bound result, in the paper "The Johnson-Lindenstrauss lemma and the sphericity of some graphs," by Frankl and Maehara, Journal of Combinatorial Theory, Series B,Volume 44, Issue 3, 1988, Pages 355–362.

if $G$ is a graph on $n$ vertices and with smallest eigenvalue $\lambda$ then its sphericity sph$(G)$ is less than $c \lambda^2 \log n$.

If you can realize $G$ by touching balls in $\mathbb{R}^d$, then you have established its sphericity is at most $d$.

Answer 3

It should be doable with constant radii in $\mathbf{R}^{n-1}$. A subgraph of the complete graph can be laid out as some of the edges of a regular simplex. At each vertex take a tiny ball (very much smaller than the length of the edges. Each ball is cut by hyperplanes through the center of the ball perpendicular to the edges (all of them) of the simplex. Combinatorially, the hyperplanes in each ball behave like the coordinate hyperplanes. Thus each ball is cut into regions that cover all combinations of being closer to or farther from the other vertices of the simplex. For each vertex choose a region that is closer to those vertices that are neighbors in the desired subgraph of the simplex edges, and farther if not. Now for the belief part. It should be true that for some distance only slightly smaller than the edge length, points in the chosen regions (one per each) can be found of that distance if an edge is desired, and farther than that distance if an edge is not desired.