Crossings in grid drawings (Q405129)

Summary: We prove tight 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 crossing-free geometric graphs that can be drawn on such grids.{ }In particular, we show that any geometric graph with \(m\geq 8N\) edges and with vertices on a 3D integer grid of volume \(N\), has \(\Omega((m^2/N)\log(m/N))\) crossings. In \(d\)-dimensions, with \(d\geq 4\), this bound becomes \(\Omega(m^2/N)\). We provide matching upper bounds for all \(d\). Finally, for \(d\geq 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^{\Theta(N)}\). In 3 dimensions it remains open to improve the trivial bounds, namely, the \(2^{\Omega(N)}\) lower bound and the \(N^{O(N)}\) upper bound.