{"id":"arxiv/2611.01509","url":"https://arxiv.org/abs/2611.01509","tags":["math.CO","cs.CG"],"score":0,"title":"Every $k$-Quasi-Planar Graph Has Linearly Many Edges","domain":"math.CO","source":"arxiv","authors":["Ankan Sadhu"],"reviews":0,"subject":"math.CO","summary":"For every fixed integer $k\\ge2$, we prove that every simple graph on $n$ vertices drawn in the plane with no $k$ pairwise crossing edges has at most $C_kn$ edges, where $C_k$ depends only on $k$. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For $n\\ge3$, removing a small disk around each vertex turns the drawing into a family of arcs on a sphere with $n$ boundary circles. Each arc joins two different boundary circles, and different edges have different unordered pairs of endpoint circles. The arcs are therefore essential and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-11-01","reactions":{}}