We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has ((m^2 n) (m n)) crossings. In d-dimensions, with d >= 4, this bound becomes (m^2 n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^ (n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^ (n) lower bound and the n^O(n) upper bound.
@cite_27: An exact formula is given for the maximum number of edges in a graph that admits a three-dimensional grid-drawing contained in a given bounding box. The first universal lower bound on the volume of threedimensional grid-drawings is obtained as a corollary. Our results generalise to the setting of multi-dimensional polyline grid-drawings.
The work most closely related to the current work, in that it presents an extremal result relating crossings, volume, and number of edges, is that of Bose al @cite_27 , who show that the maximum number of edges in a crossing-free @math -D geometric grid graph, @math , with vertex set @math , is exactly For a fixed volume, @math , maximizing gives @math , in which case becomes @math . We state this here as lemma since we make use of it several times. boser immediately yields the upper-bound @math (see the beginning of counting ). It also yields the lower-bound @math since, if a geometric grid graph @math has @math we can remove an edge an edge from @math that eliminates at least one crossing. Since this can be repeated until @math has @math edges, this implies that @math has at least @math crossings.