REVIEW 3 major objections 4 minor 25 references
On the maximum number of edges of outer k-planar graphs
T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read An outer k-planar graph has at most $(\sqrt{2}+\varepsilon)\sqrt{k}\,n + n$ edges, with $\varepsilon\to 0$, improving the previous best constant $2.465$ to an asymptotic constant of $\sqrt{2}$.
desk verdict New best constant for outer k-planar edge density, from about 2.465√k down to (√2+ε)√k; the central proof holds, but the write-up needs corrections before publication. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The carrying object is the shortest diagonal of length at least $l_0 = \sqrt{2}\,\sqrt{k}$, denoted $D$. The argument relies on the counting inequality that the smaller region $G_1$ contains at most $\sum_{p=2}^{l_0}(l+2-p)$ diagonals of length $p$, and that the complementary region $G_2$, by minimality of the counterexample, contains at most $x(n-l+2)$ diagonals. Subtracting these from the total diagonal count yields a lower bound on the number of diagonals crossing $D$; the choice of $l_0$ and $x=(\sqrt{2}+\varepsilon)\sqrt{k}$ makes this lower bound exceed $k$ for large $k$, yielding the contradiction.
What would settle it
Take a family of outer $k$-planar graphs, split each along a shortest diagonal of length at least $\sqrt{2}\,\sqrt{k}$, and count the length-one diagonals in the smaller region. If any family has more than $(l_0-1)(2l-l_0+2)/2$ such diagonals, the main inequality fails; the concatenated-$K_x$ lower-bound construction is a concrete test case.
Extended reading notes
Core claim
The main theorem, Theorem 10, states that an outer $k$-planar graph has at most $(\sqrt{2}+\varepsilon)\sqrt{k}\,n$ diagonals, where $\lim_{k\to\infty}\varepsilon = 0$. The proof takes a vertex-minimal counterexample, chooses a shortest diagonal whose length is at least $l_0 = \sqrt{2}\,\sqrt{k}$, and splits the graph along it into two regions. It then counts diagonals in the smaller region by length, bounding the number of length-$p$ diagonals by $l+2-p$, and uses minimality of the counterexample to bound the larger region. Combining these bounds forces the chosen diagonal to be crossed by more than $k$ diagonals, contradicting $k$-planarity for sufficiently large $k$.
Load-bearing premise
The proof assumes that the diagonals in the smaller region can be counted by length with at most $l+2-p$ diagonals of length $p$, and implicitly that diagonals of length one either do not occur or are negligible; if a dense construction puts many length-one diagonals in that region, the forced crossing count could drop below $k$.
Editorial extensions
If this is right
- Every outer $k$-planar graph on $n$ vertices has at most $(\sqrt{2}+\varepsilon)\sqrt{k}\,n + n$ edges for sufficiently large $k$, improving the previous best of about $2.465\sqrt{k}\,n$ edges.
- The known lower bound construction of $\sqrt{k}\,n + \Theta(1)$ edges remains the best known, so the gap between lower and upper bound constants shrinks from roughly $2.465$ to $\sqrt{2}$.
- The minimum-degree bound $2\sqrt{k+1}+2$ implies that every convex geometric $k$-plane graph can be colored with $\lfloor 2\sqrt{k+1}\rfloor + 1$ colors.
- For bipartite outer $k$-planar graphs, the local approach gives at most $2\sqrt{8/11}\,\sqrt{k}\,n \approx 1.7\sqrt{k}\,n$ edges for sufficiently large $k$.
- The bound $\mathrm{mc}(C_n^{1,2,\dots,r}) \le (5r/8 + 76)n$ on the maximum cut of circulant graphs is a standalone result that could serve other extremal graph problems.
Reading between the lines
- Editorial extension: if the counting of length-one diagonals in the smaller region is handled carefully, the same shortest-long-diagonal method could yield explicit finite-$k$ bounds rather than only an asymptotic statement.
- Editorial extension: the circulant max-cut estimate is proved without boundary conditions; incorporating boundary terms directly into Problem 1 could push the bipartite direct approach below the general bound.
- Editorial extension: the asymmetry between the lower bound constant $1$ and the upper bound constant $\sqrt{2}$ suggests that the true maximum might lie at $\sqrt{k}\,n$, but the current method cannot reach that constant without a more delicate count of short diagonals.
- Editorial extension: the same diagonal-counting strategy might transfer to non-convex $k$-planar graphs, where no analogue of a shortest long diagonal is currently used.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the maximum number of edges of an outer k-planar graph, i.e., a straight-line drawing of a graph on n points in convex position in which every edge crosses at most k other edges. The main contribution is a direct counting argument giving an upper bound of (√2+ε)√k n diagonals for sufficiently large k with ε→0, hence (√2+ε)√k n+n edges, improving the previous best 2.465√k n. The paper also gives three other upper-bound approaches with constants 2.85, 2.34, and 2√(k+1)+2, a small-k table, and a bipartite version of the problem. The bipartite part uses a maximum-cut bound for circulant graphs C_n^{1,...,r} and derives bounds for consecutive and alternating bipartite settings.
Significance. The claimed asymptotic bound √2√k n + n, if correct, is a substantial improvement over the previous best 2.465√k n and matches the order of the known lower bound √k n up to the constant. The proof is self-contained modulo known crossing lemmas and the cited spectral max-cut bound, and it does not rely on the author's own prior work for its main claim. The circulant maximum-cut lemma and the bipartite bounds are of independent interest. However, the manuscript contains several algebraic and range-of-validity errors in central and auxiliary proofs, so the current version needs revision before the results can be accepted.
major comments (3)
- [§5.2 (Theorem 19)] The proof of Theorem 19 does not support the stated range k≥5. From m>2.228√k n one obtains |E(G')|> (4.456√k −1)n, not (4.06√k + (0.45√k−1))n; the displayed equality is algebraically false. Moreover, comparing the lower bound with 5.243√k n (the constant of Lemma 2) is inappropriate because Lemma 18 gives the relevant bound 4.06√k n. With Lemma 18, the argument yields a contradiction only when 4.456√k −1 > 4.06√k, i.e., k≥7. The theorem should be restated for k≥7 or supplied with a different argument.
- [§3.5 (Theorem 10)] The derivation of the main inequality contains a false equality. After substituting l0=√2√k, the lower bound on the number of crossings is (ε√k+1)l + k+1 −2ε√k −(7√2/2)√k, not k+1+ε√k l−2(√2+ε)√k−0.5√2√k. The displayed expression can be used as a (weaker) lower bound after replacing l by l0 in the linear term, but this replacement and the resulting inequality need to be stated explicitly. The asymptotic conclusion is unaffected, but as written the central chain of inequalities is not derivable.
- [§4 (Lemma 12)] The numerical claim that f(176)≈−0.4997 does not follow from the displayed formula f(r)=1/r+C0−8π²/(r+1) with C0≥−0.4344; for r=176 that expression is approximately −0.875 (or, with a squared denominator, about −0.431). Since the proof of Lemma 12 relies on f(176)>−1/2, the stated Mercer bound or its evaluation must be corrected. This is relevant for the bipartite upper bounds that use Lemma 12.
minor comments (4)
- [Theorem 20] In Theorem 20, the statement writes −(2k+5) in the numerator, but the proof derives −(2k+6) and the subsequent list of bounds for k=0,...,4 is consistent only with −(2k+6).
- [§3.5 (Theorem 10)] In the proof of Theorem 10, the terms 'length two' and 'length three' are shifted by one relative to the definition of length in §2; the count of diagonals in G1 is correct after the intended reindexing, but the terminology should be clarified so the reader does not infer that length-1 diagonals are omitted.
- [Throughout] There are several typos: 'meassured' in §3.5, 'imaginery' in §4, 'sraphs' in reference [14], and in Lemma 12 the Dirichlet kernel is written as D_r(2πk/n) although k has already been used for the summation index.
- [Theorem 15] In Theorem 15, '\lfloor\sqrt{k}/2\rfloor' should presumably be '\lfloor\sqrt{k/2}\rfloor' to match the stated asymptotic 0.707√k n.
Circularity Check
No significant circularity: the main bound in Theorem 10 is a self-contained minimal-counterexample argument; the only self-citation is peripheral.
full rationale
The central claim (Theorem 10 and Corollary 11) is derived by a minimal-counterexample counting argument. The bound on the smaller side G2 is justified by vertex-minimality as an induction hypothesis, not by assuming the theorem; the count of diagonals inside G1 is a direct combinatorial bound by length, and the asymptotic coefficient emerges from solving the resulting inequality. No fitted parameter is relabeled as a prediction, and no defining equation makes the target equivalent to an input. The small-k bounds and crossing lemmas used in the earlier variants come from independent sources [2, 5, 7, 8, 21, 23]. The only citation to the author's own prior work is [10], which supplies the bipartite crossing-lemma constant 1024/16875 used in Lemma 18 and Theorem 19; this supports a peripheral bipartite variant rather than the main general bound, and the constant is an externally derived result from a separate paper rather than a self-referential premise. Thus no circular reduction is present in the main derivation chain.
Assumptions & free parameters
free parameters (3)
- l0 =
sqrt(2)*sqrt(k)
- epsilon =
arbitrary positive; tends to 0 as k grows
- constant 76 in Lemma 12 =
76
assumptions (5)
- standard math Crossing Lemma for multigraphs with multiplicity two (Szekely; Buengener-Kaufmann)
- standard math Mohar-Poljak eigenvalue bound mc(G) <= (1/4) lambda_max(L) n
- standard math Mercer's lower bound on the minimum of the Dirichlet kernel
- domain assumption Known tight upper bounds for non-homotopic k-planar multigraphs for k<=3 (folklore, [7], [6], [21])
- standard math In any bipartite outerplanar graph, the number of internal faces is at most n/2
Cite this review
Pith. "Pith review of On the maximum number of edges of outer k-planar graphs." pith.science (2026). https://pith.science/paper/VHYE3CGS
@misc{pith2026250524490,
author = {Pith},
title = {Pith review of: On the maximum number of edges of outer k-planar graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/VHYE3CGS}},
note = {Machine review of arXiv:2505.24490}
}
abstract
We study the maximum number of straight-line segments connecting $n$ points in convex position in the plane, so that each segment intersects at most $k$ others. This question can also be framed as the maximum number of edges of an outer $k$-planar graph on $n$ vertices. We outline several approaches to tackle the problem with the best approach yielding an upper bound of $(\sqrt{2}+\varepsilon)\sqrt{k}n$ edges (with $\varepsilon \rightarrow 0$ for sufficiently large $k$). We further investigate the case where the points are arbitrarily bicolored and segments always connect two different colors (i.e., the corresponding graph has to be bipartite). To this end, we also consider the maximum cut problem for the circulant graph $C_n^{1,2,\dots,r}$ which might be of independent interest.
Reference graph
Works this paper leans on
- [2]
-
[23]
Ábrego, B.M., Dandurand, J., Fernández-Merchant, S., Lagoda, E., Sapozhnikov, Y.: Book crossing numbers of the complete graph and small local convex crossing numbers (2024), https://arxiv.org/abs/1607.00131
work page Pith review arXiv 2024
-
[11]
Capoyleas, V., Pach, J.: A turán-type theorem on chords of a convex polygon. Journal of Combinatorial Theory, Series B 56(1), 9--15 (1992), https://www.sciencedirect.com/science/article/pii/009589569290003G
arXiv 1992
-
[10]
B \" u ngener, A., Pfister, M.: On the edge density of bipartite 3-planar and bipartite gap-planar graphs. In: GD . LIPIcs, vol. 320, pp. 28:1--28:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik (2024)
work page 2024
-
[1]
Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85 (2019)
work page 2019
-
[3]
Angelini, P., Lozzo, G.D., F \" o rster, H., Schneck, T.: 2-layer k-planar graphs density, crossing lemma, relationships and pathwidth. Comput. J. 67(3), 1005--1016 (2024)
work page 2024
- [4]
-
[5]
Algorithmica 74(4), 1293--1320 (2016), https://doi.org/10.1007/s00453-015-0002-1
Auer, C., Bachmaier, C., Brandenburg, F.J., Glei ner, A., Hanauer, K., Neuwirth, D., Reislhuber, J.: Outer 1-planar graphs. Algorithmica 74(4), 1293--1320 (2016), https://doi.org/10.1007/s00453-015-0002-1
Show all 25 references
-
[6]
Bekos, M.A., Kaufmann, M., Raftopoulou, C.N.: On the density of non-simple 3-planar graphs. In: GD . Lecture Notes in Computer Science, vol. 9801, pp. 344--356. Springer (2016)
2016
-
[7]
In: SoCG
Bekos, M.A., Kaufmann, M., Raftopoulou, C.N.: On optimal 2- and 3-planar graphs. In: SoCG. LIPIcs, vol. 77, pp. 16:1--16:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik (2017)
2017
-
[8]
B \" u ngener, A., Kaufmann, M.: Improving the crossing lemma by characterizing dense 2-planar and 3-planar graphs. In: GD . LIPIcs, vol. 320, pp. 29:1--29:22. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik (2024)
2024
-
[9]
u ngener, A., Kaufmann, M.: Improving the crossing lemma by characterizing dense 2-planar and 3-planar graphs. In: GD. Schloss Dagstuhl – Leibniz-Zentrum f\
B\" u ngener, A., Kaufmann, M.: Improving the crossing lemma by characterizing dense 2-planar and 3-planar graphs. In: GD. Schloss Dagstuhl – Leibniz-Zentrum f\" u r Informatik (2024)
2024
-
[12]
In: International Symposium on Graph Drawing and Network Visualization
Chaplick, S., Kryven, M., Liotta, G., L \"o ffler, A., Wolff, A.: Beyond outerplanarity. In: International Symposium on Graph Drawing and Network Visualization. pp. 546--559. Springer (2017)
2017
-
[13]
CoRR abs/1708.08723 (2017), http://arxiv.org/abs/1708.08723
Chaplick, S., Kryven, M., Liotta, G., L \" o ffler, A., Wolff, A.: Beyond outerplanarity. CoRR abs/1708.08723 (2017), http://arxiv.org/abs/1708.08723
2017 arXiv
-
[14]
In: STOC
Gon c alves, D.: Edge partition of planar sraphs into two outerplanar graphs. In: STOC . pp. 504--512. ACM (2005)
2005
-
[15]
Foundations and Trends® in Communications and Information Theory 2(3), 155--239 (2006), http://dx.doi.org/10.1561/0100000006
Gray, R.M.: Toeplitz and circulant matrices: A review. Foundations and Trends® in Communications and Information Theory 2(3), 155--239 (2006), http://dx.doi.org/10.1561/0100000006
2006 doi
-
[16]
prove that one of them intersects at least 10000 others
abacaba (https://math.stackexchange.com/users/1018325/abacaba): 200n diagonals are drawn in a convex n -gon. prove that one of them intersects at least 10000 others. Mathematics Stack Exchange, https://math.stackexchange.com/q/4767941, uRL:https://math.stackexchange.com/q/4767...
2023
-
[17]
Kokhas, K., Khrabrov, A., Berlov, S., Ivanov, S., Karpov, D., Petrov, F.: Problems of the Saint Petersburg School Olympiad in Mathematics, 2004 (2004)
2004
-
[18]
Mercer, I.D.: http://www.idmercer.com/dirichletkernel.pdf
-
[19]
Czechoslovak Mathematical Journal 40(2), 343--352 (1990), http://eudml.org/doc/13856
Mohar, B., Poljak, S.: Eigenvalues and the max-cut problem. Czechoslovak Mathematical Journal 40(2), 343--352 (1990), http://eudml.org/doc/13856
1990
-
[20]
Pach, J., T \' o th, G.: Graphs drawn with few crossings per edge. Comb. 17(3), 427--439 (1997)
1997
-
[21]
Sone, K., Suzuki, Y.: Optimal 1-planar multigraphs. Discret. Math. 346(10), 113553 (2023)
2023
-
[22]
Sz \' e kely, L.A.: Crossing numbers and hard erd \" o s problems in discrete geometry. Comb. Probab. Comput. 6(3), 353--358 (1997)
1997
-
[24]
, " * write output.state after.block = add.period write
ENTRY address author booktitle chapter edition editor eid howpublished institution journal key month note number organization pages publisher school series title type url volume year label INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.s...
-
[25]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.