Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
<|reference_start|>Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs: 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.<|reference_end|>
@article{büngener2024improving,
    title={Improving the Crossing Lemma by Characterizing Dense 2-Planar and
  3-Planar Graphs},
    author={Aaron B"ungener and Michael Kaufmann},
    journal={arXiv preprint arXiv:2409.01733},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.01733},
    primaryClass={math.CO cs.DM}
}