4 edited body

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

3 added 321 characters in body

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

2 added 246 characters in body

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.

1