Answers are grounded in this paper and cite their sources.
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ₖ(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 kO(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²n) edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.
No takes yet. Share an insight, caveat, or question.
Milojević et al. (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: