Every k-Quasi-Planar Graph Has Linearly Many Edges
Abstract
For every fixed integer k≥2, we prove that every simple graph on n vertices drawn in the plane with no k pairwise crossing edges has at most Ckn edges, where Ck depends only on k. We allow any finite number of proper crossings between two edges, including edges with a common endpoint. For n≥3, 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 pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most k−1. Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the n-holed sphere has linearly many edges and triangles.
Related
- Edges of the uniform random forest of Kn are pairwise negatively correlated for every n
- Planar intrusions from a narrow, jet-like source in a linearly stratified ambient
- Strongly separating graph edges with 10n paths
- The chromatic number of a random graph with o(n3/2) edges
- Planar Gross--Pitaevskii traveling waves at every subsonic speed
BibTeX
@misc{sadhu2026every,
title = {{Every $k$-Quasi-Planar Graph Has Linearly Many Edges}},
author = {Ankan Sadhu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01509},
eprint = {2611.01509},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01509},
}
RIS
TY - UNPB
TI - Every k-Quasi-Planar Graph Has Linearly Many Edges
AU - Ankan Sadhu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01509
UR - https://arxiv.org/abs/2611.01509
AB - For every fixed integer k≥2, 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≥3, 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 pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy. Any family of pairwise intersecting lifts to the universal cover projects to distinct graph edges that cross pairwise. Its size is consequently at most k−1. Beeker and Lazarovich's theorem on surface patterns then bounds the number of arcs. Their estimate is linear in the size of a triangulation, and an explicit triangulation of the n-holed sphere has linearly many edges and triangles.
ER -