Paperlane

no. 10 · Friday 6 November 2026

On the number of edges in quasiplanar graphs

János Pach, Gábor Tardos and Ji Zeng

math.CO

Abstract

A $k$-quasiplanar graph is a graph drawn in the plane with no $k$ pairwise crossing edges. Pach, Shahrokhi, and Szegedy conjectured that every such graph on $n$ vertices has $O_k(n)$ edges. ChatGPT produced a proof of this conjecture. Here, we present a simplified, self-contained version of that proof.

fields
Combinatorics
pdf ↗ page arXiv:2611.07314 ↗