Id: arxiv/2611.21416 Url: https://arxiv.org/abs/2611.21416 Tags: math.CO, cs.CG Score: 0 Title: Polynomial bounds for quasiplanar graphs Domain: math.CO Source: arxiv Authors: Aleksa Milojević, Patryk Morawski, Benny Sudakov, Istvan Tomon Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-11-16 Page: https://delphi.science/r/arxiv/2611.21416 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…