Metraipolis › archive › dc_bc2c71b7a32b
Every $k$-Quasi-Planar Graph Has Linearly Many Edges — arXiv:2611.01509
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.01509
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:49:44.241Z
- SHA-256 of the archived text
7890f5ca3c7ddb382d9181b039a0d14984a09df302d1022e41a279418883cbc2- Stable URL of this page
https://metraipolis.com/documento/dc_bc2c71b7a32b
How to cite
Every $k$-Quasi-Planar Graph Has Linearly Many Edges — arXiv:2611.01509 — arXiv (en), https://arxiv.org/abs/2611.01509 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc2c71b7a32b (Metraipolis archive dc_bc2c71b7a32b, sha256 7890f5ca3c7ddb382d9181b039a0d14984a09df302d1022e41a279418883cbc2)
BibTeX
@misc{dcbc2c71b7a32b,
title = {Every $k$-Quasi-Planar Graph Has Linearly Many Edges — arXiv:2611.01509},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.01509},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc2c71b7a32b; sha256 7890f5ca3c7ddb382d9181b039a0d14984a09df302d1022e41a279418883cbc2},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.01509. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 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. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno). Categorie arXiv: Combinatorics (math.CO) ; Computational Geometry (cs.CG). Pagina del lavoro: https://arxiv.org/abs/2611.01509 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-03T18:15:38.072Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).