Crossings in Grid Drawings

Abstract

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\ge 4$, this bound becomes $\Omega(m^2/N)$. We provide matching upper bounds for all $d$. Finally, for $d\ge 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.