← 研踪 PaperTrailarXiv:2611.21416 · v1
Polynomial bounds for quasiplanar graphs
首次提交 2026-11-17 01:05
版本更新 2026-11-17 01:05
雷达观测 2026-11-17 16:10
摘要
A graph is -quasiplanar if it can be drawn in the plane without pairwise crossing edges. It was a longstanding conjecture that -vertex -quasiplanar graphs have 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 -quasiplanar graphs have at most edges. In this note, we greatly improve the dependence on and show that every -quasiplanar -vertex graph has at most edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.
作者备注:11 pages
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-17 01:05 · 最新观测版本
Polynomial bounds for quasiplanar graphs
A graph is -quasiplanar if it can be drawn in the plane without pairwise crossing edges. It was a longstanding conjecture that -vertex -quasiplanar graphs have 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 -quasiplanar graphs have at most edges. In this note, we greatly improve the dependence on and show that every -quasiplanar -vertex graph has at most edges. The proof is based on a geometric charging scheme and Erdős-Szekeres type combinatorial arguments.
查看此版本解读 →查看此版本原文 ↗