Polynomial bounds for quasiplanar graphs
A graph $G$ is $k$-quasiplanar if it can be drawn in the plane without $k$ pairwise crossing edges. It was a longstanding conjecture that $n$-vertex $k$-quasiplanar graphs have $O_k(n)$ edges. This was recently resolved by Sadhu and, independently, by Pach, Tardos, and Zeng, based on a theorem in topology proven by Beeker and Lazarovich. These papers showed that $k$-quasiplanar graphs have at most $k^{O(k)}n$ edges. In this note, we greatly improve the dependence on $k$ and show that every $k$-quasiplanar $n$-vertex graph has at most $O(k^2n)$ edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.
Authors
- István Tomon (ORCID: https://orcid.org/0000-0001-8344-3592)
- Aleksa Milojević (ORCID: https://orcid.org/0009-0007-0130-2114)
- Patryk Morawski
- Benny Sudakov
Publication Details
- Journal
- arXiv (Cornell University)
- Published
- 2026-11-16
- DOI
- https://doi.org/10.48550/arxiv.2611.21416
- Primary Topic
- Limits and Structures in Graph Theory
- Type
- preprint