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 crossings 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.

The crossing number inequality states that, for an undirected simple graph G with n vertices and e edges such that e > 7n, the crossing number cr(G) obeys the inequality

The constant 29 is the best known to date, and is due to Ackerman. For earlier results with weaker constants see Pach & Tóth (1997) and Pach et al. (2006).

The constant 7 can be lowered to 4, but at the expense of replacing 29 with the worse constant of 64.

The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science.

...
Wikipedia