Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs

Abstract

The classical Crossing Lemma by Ajtai et al.~and Leighton from 1982 gave an important lower bound of $c\frac{m^3}{n^2}$ for the number of crossings in any drawing of a given graph of $n$ vertices and $m$ edges. The original value was $c=1/100$, which then has gradually been improved. Here, the bounds for the density of $k$-planar graphs played a central role. Our new insight is that for $k=2,3$ the $k$-planar graphs have substantially fewer edges if specific local configurations that occur in drawings of $k$-planar graphs of maximum density are forbidden. Therefore, we are able to derive better bounds for the crossing number $\text{cr}(G)$ of a given graph $G$. In particular, we achieve a bound of $\text{cr}(G)\ge \frac{37}{9}m-\frac{155}{9}(n-2)$ for the range of $5n<m\le 6n$, while our second bound $\text{cr}(G)\ge 5m-\frac{203}{9}(n-2)$ is even stronger for larger $m>6n$. For $m>6.77n$, we finally apply the standard probabilistic proof from the BOOK and obtain an improved constant of $c>1/27.48$ in the Crossing Lemma. Note that the previous constant was $1/29$. Although this improvement is not too impressive, we consider our technique as an important new tool, which might be helpful in various other applications.