{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-16","reactions":{}}