Every $k$-Quasi-Planar Graph Has Linearly Many Edges
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.01509
curl -X POST /api/v1/records/arxiv/2611.01509/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.01509/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'