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+2sqrt3)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.
No comments:
Post a Comment