Graphs of Tangent Spheres

Question

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a circle packing whose graph is G. What happens when circles are replaced by spheres? By spheres of higher dimension? What is known about the graphs that are formed in this case? I know that they must contain all planar graphs but that is about it.

Let me update this. Based on the answer to this question I am beginning to think about the maximalchromatic number of this graph. If its edge density is less than 7 than for all graphs of this type there must be a point with 13 or less edges. Assume that there is such a graph with chromatic number greater than 14 then look at a graph with the minimum number of points with chromatic number greater than 14. One point must have 13 or less edges. Remove it and since the graph had minimum number of points to have chromatic number greater than 14 the new graph must have chromatic number 14 or less. Color it with 14 or less colors. Add the removed point and look at the colors of the thirteen points it is adjacent to give it the remaining color then we have a 14 coloring of the graph and hence a contradiction. So the chromatic number must be 14 or less. We have an lower bound of 4 as the graphs of tangent spheres contain the graphs of tangent circles which are the planar graphs which contain graphs with chromatic number four.

As we increase the dimensions of the tangent spheres the chromatic number goes to infinity just take $d+1$ tangent spheres. But I think we can do better than that for one thing we should be able to improve the lower bound from 4. Also I think there should be examples from lattices that give better lower bounds on the chromatic number possibly exponential.

Finally based on the existing chromatic numbers I am wondering if it is possible to answer this question. Is there a dimension where the chromatic number of the unit distance graph is different from the chromatic number of the graphs in that dimension of tangent spheres. The unit distance graph is the set of all points in the $n$-dimensional space with two points connected if their distance is one. For dimension two the chromatic number is known to be in the range from 4 to 7. For dimension three the range is 6 to 15. For the graphs of tangent circles we have a chromatic number of 4 and for spheres a range from 4 to 15. So the possibility that the chromatic numbers of the two types of graphs are the same has not yet been eliminated. So the specific question is what is known and what can be proved about the chromatic number of the graphs of tangent spheres.

Answer 1

The number of edges in such a graph is linear in the number of vertices, and they can be split into two equal-sized subgraphs by the removal of $O(n^{\frac{d-1}{d}})$ vertices. See e.g.

A deterministic linear time algorithm for geometric separators and its applications. D. Eppstein, G.L. Miller, and S.-H. Teng. Fundamenta Informaticae 22:309-330, 1995.

Unlike in the 2d case (where we know that the maximum number of edges such a graph can have is 3n-6) the precise maximum edge density is not known even in 3d. There's a lower bound of roughly $\frac{3828n}{607}\approx 6.3064n$ in another of my papers,

Fat 4-polytopes and fatter 3-spheres. D. Eppstein, G. Kuperberg, and G. Ziegler. arXiv:math.CO/0204007. Discrete Geometry: In honor of W. Kuperberg's 60th birthday, Pure and Appl. Math. 253, Marcel Dekker, pp. 239-265, 2003.

and an upper bound of $(4+2\sqrt3)n \approx 6.8284n$ in

Greg Kuperberg and Oded Schramm, Average kissing numbers for non-congruent sphere packings, Math. Res. Lett. 1 (1994), no. 3, 339–344, arXiv:math.MG/9405218.