A first view on the density of 5-planar graphs

Aaron B\"ungener; Jakob Franz; Maximilian Pfister; Michael Kaufmann

arxiv: 2505.24364 · v2 · pith:UWS4KC6Znew · submitted 2025-05-30 · 💻 cs.DM · math.CO

A first view on the density of 5-planar graphs

Aaron B\"ungener , Jakob Franz , Michael Kaufmann , Maximilian Pfister This is my paper

Pith reviewed 2026-05-22 02:33 UTC · model grok-4.3

classification 💻 cs.DM math.CO

keywords 5-planar graphsedge densitydischarging methodcrossing lemmagraph drawingk-planar graphs

0 comments

The pith

Graphs drawable with five crossings per edge have at most 7(n-2) edges.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper sets out to find the maximum number of edges a 5-planar graph on n vertices can have. It uses a discharging technique that is simplified because the structure of dense 5-planar graphs turns out to differ from the uniform pattern seen in graphs with one to four crossings allowed per edge. This leads to a bound of 7(n-2) edges, which a reader would care about since it refines limits useful for graph drawing and improves the constant in the Crossing Lemma from 1/27.48 to 1/27.3. The method is also demonstrated on 4-planar and 6-planar graphs.

Core claim

We show that graphs that admit a simple 5-planar drawing have at most 7(n-2) edges. This result follows from a simplified discharging technique after noting that the structure of maximally dense 5-planar graphs differs from the known uniform structure for 1 ≤ k ≤ 4.

What carries the argument

Simplified discharging technique on the denser parts of 5-planar graphs, exploiting their non-uniform structure to derive the edge bound.

If this is right

The bound improves the previous best of approximately 8.3n to 7(n-2).
This implies a small improvement of the leading constant in the Crossing Lemma from 1/27.48 to 1/27.3.
The technique applies to 4-planar and 6-planar graphs as well.
Outer 5-planar graphs can be bounded using the simplified version of the technique.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The structural difference observed for k=5 may point to a change in how density behaves as the allowed crossings increase.
Similar discharging simplifications could be explored for even larger k.
Better bounds like this may help in practical graph visualization tools that allow controlled crossings.

Load-bearing premise

The denser subconfigurations in 5-planar graphs have a structure different enough from smaller k to let a simplified discharging proof cover all cases without gaps.

What would settle it

A counterexample would be a simple 5-planar graph on n vertices with strictly more than 7(n-2) edges.

read the original abstract

A key concept for many graph layout algorithms is planarity, a graph property that allows to draw vertices and edges crossing-free in the plane. Important is the generalization to $k$-planar graphs, which can be drawn in the plane with at most $k > 0$ crossings per edge. One of the basic graph properties that have been explored for those graph classes is the maximum edge density, i.e., the maximum number of edges a $k$-planar graph on $n$ vertices may have. While there are numerous results for the classes of $1$- and $2$-planar graphs, there are few results for increasing $k=3$ or $4$ due to the complex graph structures. We make a first step towards even larger $k>4$ exploring the class of $5$-planar graphs. While our main tool is still a discharging technique, a better understanding of the structure of the denser parts leads to corresponding density bounds in a much simpler way. We first apply a simplified version of our technique to outer $5$-planar graphs and surprisingly observe that the structure of maximally dense (general) $5$-planar graphs differs from the known uniform structure of maximally dense $k$-planar graphs for smaller $1 \leq k \leq 4$. As the central result of this paper, we then show that graphs that admit a simple 5-planar drawing have at most $7(n-2)$ edges, drastically improving the previous best bound of $\approx8.3n$. This even implies a small improvement of the leading constant in the Crossing Lemma $cr(G) \ge c \frac{m^3}{n^2}$ from $c=\frac{1}{27.48}$ to $c=\frac{1}{27.3}$. To demonstrate the potential of our new technique, we also apply it to 4-planar and 6-planar graphs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper establishes m ≤ 7(n-2) for simple 5-planar graphs by exploiting a non-uniform structure that simplifies discharging, plus a minor lift to the Crossing Lemma constant.

read the letter

The main thing to know is that simple 5-planar graphs have at most 7(n-2) edges. This improves the earlier general bound of roughly 8.3n and nudges the Crossing Lemma constant from 1/27.48 to 1/27.3. The authors reach the bound by first handling outer 5-planar graphs, then observing that the densest general 5-planar instances lack the uniform maximal structure known for k from 1 to 4. That difference lets them run a lighter discharging scheme without the usual heavy casework. They also sketch how the same idea applies to 4-planar and 6-planar graphs, which shows the technique is not tied to one value of k. The structural observation itself is the clearest novelty here and explains why the argument stays manageable at k=5. The discharging looks standard and the target bound is explicit, so the claim is easy to check in principle once the cases are written out. The soft spot is exactly the completeness of those cases. The argument needs every local configuration—high-degree vertices near clusters of crossings, faces touching several crossings, and so on—to end with non-negative charge after redistribution. If the claimed structural difference leaves out even one dense subconfiguration, the Euler-derived initial charge will not balance and the global bound fails. The abstract states the difference but does not list the configurations, so a referee must confirm that the case analysis is exhaustive rather than optimistic. This work is aimed at people who need concrete density bounds for drawing algorithms or small improvements to crossing-number inequalities. A reader already working on k-planar graphs or discharging arguments will find the structural shift useful to test on other values of k. It deserves a serious referee because the result is new, the method is reproducible, and the improvement is concrete even if modest. I would send it to review.

Referee Report

1 major / 3 minor

Summary. The manuscript claims that simple 5-planar graphs on n vertices have at most 7(n-2) edges. The proof uses a discharging argument that exploits an observed structural difference: maximally dense 5-planar graphs lack the uniform structure of k-planar graphs for 1 ≤ k ≤ 4, permitting a simplified redistribution scheme. The authors first establish a bound for outer 5-planar graphs via this technique, then extend it to general simple 5-planar graphs; they also apply the method to 4-planar and 6-planar graphs and derive a modest improvement to the leading constant in the Crossing Lemma.

Significance. If the central bound holds, the result improves the best previous density estimate for 5-planar graphs from roughly 8.3n to 7(n-2) and yields a small but concrete strengthening of the Crossing Lemma constant from 1/27.48 to 1/27.3. The structural observation and the resulting simplified discharging constitute a reusable technique whose potential is illustrated by the additional applications to 4- and 6-planar graphs. The derivation is parameter-free and rests on Euler’s formula plus explicit charge redistribution.

major comments (1)

[Section 4 (main discharging argument for 5-planar graphs)] The central claim m ≤ 7(n-2) rests on the completeness of the case analysis under the claimed non-uniform structure. The manuscript must verify that every local configuration (high-degree vertices, clusters of crossings, faces incident to multiple crossings) receives non-negative final charge; an explicit enumeration or table of all considered reducible configurations would allow independent verification that no dense subconfiguration produces a deficit.

minor comments (3)

[Abstract] The abstract states the bound and the discharging method but supplies no proof details, error analysis, or verification steps; a short outline of the initial charge function and the redistribution rules in the introduction would improve readability.
[Section 3] Notation for the number of crossings per edge and for the final charge after redistribution should be introduced once and used consistently; occasional reuse of the same symbol for different quantities appears in the outer-5-planar section.
[Figures 2 and 3] Figure captions for the illustrative drawings of dense 5-planar subgraphs should explicitly label the crossings and the vertices whose degrees are used in the charge calculation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address the single major comment below and will incorporate the requested verification to strengthen the presentation of the discharging argument.

read point-by-point responses

Referee: [Section 4 (main discharging argument for 5-planar graphs)] The central claim m ≤ 7(n-2) rests on the completeness of the case analysis under the claimed non-uniform structure. The manuscript must verify that every local configuration (high-degree vertices, clusters of crossings, faces incident to multiple crossings) receives non-negative final charge; an explicit enumeration or table of all considered reducible configurations would allow independent verification that no dense subconfiguration produces a deficit.

Authors: We agree that an explicit enumeration or table would improve independent verifiability of the case analysis. In the revised manuscript we will add a dedicated table (or enumerated list) in Section 4 that records every local configuration examined under the observed non-uniform structure of maximally dense 5-planar graphs. For each entry we will list the initial charge, the precise redistribution rules applied, and the resulting non-negative final charge. The table will explicitly cover high-degree vertices, clusters of crossings, and faces incident to multiple crossings, thereby confirming that no dense subconfiguration produces a deficit and that the analysis supporting m ≤ 7(n-2) is complete. revision: yes

Circularity Check

0 steps flagged

No circularity: discharging proof derives bound from Euler formula and case analysis

full rationale

The paper derives the m ≤ 7(n-2) bound via a standard discharging argument on a maximal simple 5-planar graph: initial charge from Euler's formula is redistributed according to rules justified by the claimed structural difference from k≤4 cases. No step equates the target bound to a fitted parameter, renames a known result, or reduces via self-citation to an unverified premise; the final non-negative charge sum directly yields the inequality without circular reduction. The structural observation is presented as an empirical finding from the same discharging analysis rather than an input assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review performed on abstract only; no explicit free parameters, invented entities, or detailed axioms are visible.

pith-pipeline@v0.9.0 · 5890 in / 969 out tokens · 49651 ms · 2026-05-22T02:33:04.987383+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AlexanderDuality.lean alexander_duality_circle_linking unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We will redistribute the charge in several steps such that the charge of every face is non-negative and the charge of every edge is at least 2α... We obtain α=49/170 (the bottleneck being Equation 16)
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

graphs that admit a simple 5-planar drawing have at most 7(n-2) edges

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.