Crossing number inequality

In the mathematics of graph drawing, the crossing number inequality or crossing lemma gives a lower bound on the minimum number of edge crossings in a plane drawing of a given graph, as a function of the number of edges and vertices of the graph. It states that, for graphs where the number e of edges is sufficiently larger than the number n of vertices, the crossing number is at least proportional to e³/n².

It has applications in VLSI design and combinatorial geometry, and was discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi and by Leighton.