Crossing number inequality

Remarks

A planar simple graph with $n \ge 3$ vertices has at most $3n - 6$ edges by the edge bound for planar graphs. Removing one edge per crossing from a drawing gives a planar graph, so $\operatorname{cr}(G) \ge e - 3n$ for every simple graph. Now keep each vertex of an optimal drawing independently with probability $p$, as in the probabilistic method. Taking expectations in the weak bound gives $p^4 \operatorname{cr}(G) \ge p^2 e - 3pn$, and the choice $p = 4n/e$ gives the result. Example: the complete graph $K_n$ has $e = n(n-1)/2$ edges, which is at least $4n$ for $n \ge 9$, so $\operatorname{cr}(K_n) \ge c n^4$ for a constant $c > 0$. Without a hypothesis like $e \ge 4n$ the bound fails: a graph with $e = n$ edges can be a cycle, which has crossing number $0$.

Going deeper

For a student

The inequality was proved by Ajtai, Chvátal, Newborn and Szemerédi and, independently, by Leighton, in the early 1980s. Its main use in discrete geometry is through incidence bounds. László Székely used it to give short proofs of the Szemerédi–Trotter theorem on point-line incidences and of the $O(n^{4/3})$ bound in the unit distance problem. One draws the points as vertices and the pieces of lines or circles as edges, and compares the forced crossings with the number of pairs of curves.