PreprintCC BY 4.0arXiv
On the number of edges in quasiplanar graphs
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 Ok(n) edges. ChatGPT produced a proof of this conjecture. Here, we present a simplified, self-contained version of that proof.
Related
- The maximum number of edges in minimal matching covered graphs
- On rainbow saturated graphs with minimum number of edges
- Maximizing Algebraic Connectivity with 2(n−2) Edges: The Large Vertex Number Case
- On the limiting distribution of the number of improper edges for random trees
- The minimum number of wheel-saturating edges
BibTeX
@misc{pach2026number,
title = {{On the number of edges in quasiplanar graphs}},
author = {János Pach and Gábor Tardos and Ji Zeng},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.07314},
eprint = {2611.07314},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.07314},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the number of edges in quasiplanar graphs
AU - János Pach
AU - Gábor Tardos
AU - Ji Zeng
PY - 2026
DA - 2026/11/05
PB - arXiv
DO - 10.48550/arxiv.2611.07314
UR - https://arxiv.org/abs/2611.07314
AB - 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.
ER -