Paperlane

no. 14 · Friday 13 November 2026

A linear edge bound for k-quasi-planar graphs

Ankan Sadhu

math.CO · v2 · 12 pp

Abstract

We prove the $k$-quasi-planar graph conjecture for topological drawings. For every integer $k\ge 2$, a simple graph on $n\ge 3$ vertices admitting a drawing with no $k$ pairwise crossing edges has at most $1056(k-1)^2(n-2)$ edges. Thus the number of edges is linear in $n$, with an explicit quadratic dependence on $k$. The result allows multiple crossings between the same pair of edges, including edges with a common endpoint. The proof uses the double of a sphere with boundary to represent graph edges by closed geodesics on a hyperbolic surface. The endpoints of geodesic lifts induce partial orders of width at most $k-1$. A stability bound for greedy chain partitions, together with a counting argument over a triangulation, gives the stated edge bound.

comments
12 pages, 6 figure, Revision of v1
fields
Combinatorics
pdf ↗ page arXiv:2611.01509 ↗