Every $k$-Quasi-Planar Graph Has Linearly Many Edges

Ankan Sadhu

AI summary · arXiv: 2611.01509v1 · math.CO

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

Ankan Sadhu

How to read this summary? Illustrated guide

The essentials

For every fixed k ≥ 2, every simple n-vertex graph drawn without k pairwise crossing edges has at most Cₖn edges, even when pairs of edges may cross repeatedly.

Based on the abstract only: check the details in the original paper.

Question

Does forbidding k pairwise crossing edges force a linear edge bound when drawings may have repeated crossings between two edges, including edges sharing an endpoint?

Method

For n ≥ 3, the proof removes a small disk around each vertex and represents graph edges as arcs on an n-holed sphere. These arcs are essential and pairwise nonhomotopic; the Beeker–Lazarovich theorem bounds their number using a triangulation whose size is linear in n.

Findings

Result Every fixed-k quasi-planar graph in the stated drawing model has at most Cₖn edges.
See the passage in the paper
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$.
Result The result permits any finite number of proper crossings between two edges, even when they share an endpoint.
See the passage in the paper
We allow any finite number of proper crossings between two edges, including edges with a common endpoint.
Result The arcs obtained from the drawing are essential and pairwise nonhomotopic, and their endpoints may move along their boundary circles during homotopy.
See the passage in the paper
The arcs are therefore essential and pairwise nonhomotopic, with endpoints allowed to move along their boundary circles during a homotopy.
Authors’ interpretation The proof uses the bound on pairwise-intersecting lifts to apply a surface-pattern theorem and obtain the linear estimate.
See the passage in the paper
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.

Limitations

The theorem applies to simple graphs and fixed integers k ≥ 2; it does not state a bound for non-simple graphs or for k varying with n.
See the passage in the paper
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$.

Why it matters

The result extends linear edge bounds for quasi-planar graphs to drawings that allow repeated crossings between two edges, including edges with a common endpoint. Its argument connects such drawings to surface patterns and uses a triangulation of linear size.

Written by AI from the paper. Passages are checked word for word against the text we analysed; the rest may contain errors.

AI-generated keywords: Extremal graph theory graph drawings pairwise crossings surface patterns homotopy of arcs

Read further

Comprehensive Summary
Layman's Summary
Blog article
Original abstract

The paper studies a central extremal question about graph drawings: how many edges can a graph have if its drawing contains no specified number of pairwise-crossing edges? For every fixed integer $k \ge 2$, the author proves a linear upper bound in the number of vertices. Specifically, every simple graph with $n$ vertices that can be drawn in the plane without $k$ pairwise-crossing edges has at most $C_k n$ edges, where $C_k$ depends only on $k$. The abstract does not specify the value of this constant. The result applies to a permissive notion of drawing: two edges may cross any finite number of times, and edges sharing a vertex may also cross. Thus, the proof does not require edges to intersect at most once or forbid crossings between adjacent edges. The only prohibited configuration is a set of $k$ edges that cross pairwise. The graph is assumed to be simple, a condition that is important for the topological reformulation used in the proof. The method converts the drawing problem into one about curves on a surface. For graphs with at least three vertices, the author removes a small disk around each vertex. The remaining surface is a sphere with $n$ boundary circles, and each graph edge becomes an arc joining the circles corresponding to its endpoints. Since the graph is simple, distinct edges have distinct unordered pairs of endpoint circles. The resulting arcs are essential and pairwise nonhomotopic, with homotopies allowed to move arc endpoints along their boundary circles. The proof then uses the surface’s universal cover. A collection of arcs whose lifts are pairwise intersecting would project to distinct graph edges that cross pairwise in the original drawing. Because the graph contains no $k$ pairwise-crossing edges, such a collection has at most $k-1$ arcs. The author applies a theorem of Beeker and Lazarovich on surface patterns to bound the size of a family of arcs satisfying this restriction. The resulting estimate is linear in the size of a triangulation of the surface. Since the sphere with $n$ boundary circles admits a triangulation with linearly many edges and triangles, this yields the claimed $C_k n$ bound. The main conclusion is qualitative but strong: for every fixed forbidden crossing threshold $k$, a graph whose drawing avoids $k$ pairwise-crossing edges cannot have a superlinear number of edges, even when repeated crossings and crossings between incident edges are allowed. The argument connects an extremal graph-drawing problem with topological control of arcs on a punctured sphere. The supplied material includes only the title, authors, and abstract, so details beyond the abstract cannot be verified. In particular, the abstract does not give the explicit constant $C_k$, a sharper description of its dependence on $k$, lower-bound examples, or a discussion of whether the linear order is optimal for each $k$. The result is stated for fixed $k$ and establishes an existence bound rather than a numerical estimate valid for arbitrary $k$.

How Dense Can a Graph Be Without Many Mutually Crossing Edges?

A drawing of a graph can look tangled in many ways. Edges might cross repeatedly, and even two edges that share a vertex may cross elsewhere. But a more focused question asks whether the drawing contains a set of edges that all cross one another. In “Every k-Quasi-Planar Graph Has Linearly Many Edges,” Ankan Sadhu studies how many edges a graph can have if it avoids such a set.

The main result is strikingly robust: for every fixed integer k ≥ 2, a simple graph with n vertices that can be drawn without k pairwise-crossing edges has at most Ckn edges. Here, Ck is a constant that depends only on k. The abstract does not specify its value.

What Does “Pairwise-Crossing” Mean?

A collection of edges is pairwise-crossing if every two edges in the collection cross in the drawing. The condition in Sadhu’s result rules out a set of k edges with this property. It does not require the entire drawing to be free of crossings, nor does it impose the familiar restrictions that edges cross at most once or that edges sharing a vertex cannot cross.

This permissive setup makes the conclusion especially notable. Even if a drawing allows repeated intersections and crossings between incident edges, avoiding just one particular pattern—k mutually crossing edges—forces the graph to have only a number of edges proportional to its number of vertices.

From Graph Drawings to Curves on a Surface

The proof changes the language of the problem. Instead of working directly with a drawing in the plane, it turns the drawing into a family of curves on a surface.

For a graph with at least three vertices, the author removes a small disk around each vertex. What remains is a sphere with n boundary circles. Each graph edge becomes an arc joining the boundary circles associated with its endpoints.

The assumption that the graph is simple matters here. In a simple graph, there is at most one edge between any pair of vertices. Consequently, distinct edges correspond to distinct unordered pairs of boundary circles. This supports the topological reformulation used in the argument: the arcs are essential and pairwise nonhomotopic, where homotopies are allowed to slide their endpoints along the boundary circles.

Why the Universal Cover Helps

The next step uses the surface’s universal cover. In this setting, the way lifted arcs intersect can reveal a forbidden configuration in the original graph drawing. If a collection of arcs has lifts that are pairwise intersecting, those arcs project back to distinct graph edges that cross pairwise.

But the graph has no k pairwise-crossing edges. Therefore, a collection with this property can contain at most k − 1 arcs. This converts the original drawing restriction into a limit on how large certain intersecting families of arcs can be.

Sadhu then applies a theorem of Beeker and Lazarovich on patterns of arcs on surfaces. That theorem bounds the size of a family satisfying the relevant restriction in terms of the size of a triangulation of the surface. Since a sphere with n boundary circles can be triangulated using a number of edges and triangles that grows linearly with n, the resulting bound on the graph’s edges is linear as well.

What the Result Establishes—and What It Leaves Open

The paper’s central message is qualitative but powerful: fixing the forbidden crossing threshold k is enough to guarantee a linear edge bound. A graph cannot keep adding edges at a superlinear rate while still admitting a drawing that avoids k mutually crossing edges—even under a broad definition of what drawings are allowed.

The result does not, in the supplied abstract, provide an explicit value for Ck or describe precisely how that constant grows as k changes. It also does not give lower-bound examples or establish whether the linear order is optimal for every fixed k. The claim is an existence bound for each fixed threshold, not a numerical estimate that applies uniformly to arbitrary k.

Even with those details left unspecified, the proof offers a useful conceptual connection. A question about how crowded a graph drawing can become is translated into a question about how arcs behave on a punctured sphere. That shift brings tools from topology to bear on an extremal problem in graph theory—and shows how a modest restriction on crossing patterns can impose a strong limit on graph density.

Created on 09 Nov. 2026

Was this synthesis useful?

Score: 0

Ask questions about this paper to our AI assistant

How to chat with this paper? Illustrated guide

Compare with the PDF

You can also chat with multiple papers at once here.

⚠The license of the paper does not allow us to build upon its content and the AI assistant only knows about the paper metadata rather than the full article.

AI assistant instructions?

Tools for this paper

Explain it differently 1 free rewrite left today

Save to a collection Group papers in collections to compare them, chat with them and export them. Continue with Google Create a free account Log in

Export BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Advanced tools Premium

For researchers who follow a field closely: citation alerts, journal-club slides, version comparison and Zotero export. Discover Premium

Zotero

Citation alerts Citation alerts guide

Who works on it? The people and institutions who publish on its topic

Weekly letter Presented in "Mathematics and statistics this week" of 9 November 2026. Mathematics and statistics this week: Where geometry sets the limits

Journal club Premium+ Slides to present it Propose for the journal club

Versions What changed between versions

Talk about it in public Premium+ Press kit: release, questions, hype check Press kit guide

Disclaimer: The AI-based summarization tool and virtual assistant provided on this website may not always provide accurate and complete summaries or responses. We encourage you to carefully review and evaluate the generated content to ensure its quality and relevance to your needs.

Every $k$-Quasi-Planar Graph Has Linearly Many Edges

The essentials

Question

Method

Findings

Limitations

Why it matters

Read further

Definitions

How Dense Can a Graph Be Without Many Mutually Crossing Edges?

What Does “Pairwise-Crossing” Mean?

From Graph Drawings to Curves on a Surface

Why the Universal Cover Helps

What the Result Establishes—and What It Leaves Open

Ask questions about this paper to our AI assistant

Tools for this paper

Advanced tools Premium

Papers around this one

Closest papers

Prior work it builds on

Go further

Cite this paper (BibTeX)