On the Degenerate Crossing Number

The degenerate crossing number ${\text{ cr}^{*}}(G)$ of a graph $G$ is the minimum number of crossing points of edges in any drawing of $G$ as a simple topological graph in the plane. This notion was introduced by Pach and Tóth who showed that for a graph $G$ with $n$ vertices and $e \ge 4n$ edges ${\text{ cr}^{*}}(G)=\Omega \big (e^4 / n^4\big )$ . In this paper we completely resolve the main open question about degenerate crossing numbers and show that ${\text{ cr}^{*}}(G)=\Omega \big (e^3 / n^2 \big )$ , provided that $e \ge 4n$ . This bound is best possible (apart for the multiplicative constant) as it matches the tight lower bound for the standard crossing number of a graph.