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_9: We define a variant of the crossing number for an embedding of a graph G into â3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the rectilinear space crossing numbers of pseudo-random graphs.
Finally, we note that Bukh and Hubard @cite_9 have defined a form of crossing number for 3-dimensional geometric graphs that are not necessarily grid graphs. In their definition, a 4-tuple of vertex-disjoint edges form a if there is a line that intersects every edge in the 4-tuple. The , @math , of a 3-d geometric graph, @math , is the number of space crossings formed by @math 's edges. They show that a 3-d geometric graph @math with @math vertices and @math edges has a space crossing number @math . An easy lifting argument shows that this bound on the space crossing number almost implies the Crossing Lemma; specifically, it shows that the number of crossings in a graph with @math vertices and @math edges drawn in the plane is @math .