MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Return to Answer

3 Clarified upper bound argument.; deleted 208 characters in body

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, which clearly are upper bounds on your touching-ball dimension (because touching balls are intersecting spheres, and you allow different radii). 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$.

2 added 1 characters in body

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, which clearly are upper bounds on your touching-ball quantity dimension (because touching balls are intersecting spheres, and you allow different radii). 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$.

1

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, which clearly are upper bounds on your touching-ball quantity (because touching balls are intersecting spheres, and you allow different radii). 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$.