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

Aaron Büngener, Michael Kaufmann

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…