Pith. sign in

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 →

arxiv 2505.24490 v1 pith:VHYE3CGS submitted 2025-05-30 math.CO cs.DM

classification math.COcs.DM MSC 05C1005C3505C6205C50
keywords edgedensityconvexk-planegraphsouterplanarcirculantcrossingnumbermaximumcutbipartiteTurán-typeproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper studies how many straight-line segments can connect $n$ points in convex position if each segment crosses at most $k$ others, equivalently the maximum edge count of an outer $k$-planar graph. Its central claim is an upper bound of $(\sqrt{2}+\varepsilon)\sqrt{k}\,n$ diagonals, with $\varepsilon$ tending to $0$ for large $k$, which translates to at most $(\sqrt{2}+\varepsilon)\sqrt{k}\,n + n$ edges. If correct, this improves the previous best constant of about $2.465$ to about $1.414$, bringing the upper bound closer to the known lower-bound constant of $1$. The paper also derives bounds for bipartite outer $k$-planar graphs, using a new maximum-cut estimate for circulant graphs that may be useful beyond this setting.

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.

Watch

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 extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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)
  1. [§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.
  2. [§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.
  3. [§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)
  1. [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).
  2. [§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.
  3. [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.
  4. [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

0 steps flagged · score 1.0 of 10

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 3 free parameters · 5 assumptions · 0 invented entities

The paper's central results rest on standard extremal graph theory and spectral bounds, plus a few explicitly chosen ad hoc parameters (l0, epsilon, the 76 constant) that are not fitted to data. No new entities are postulated. The main risk is not circularity but the correctness of the combinatorial accounting in Theorem 10.

free parameters (3)
  • l0 = sqrt(2)*sqrt(k)
    Threshold length chosen in Theorem 10 to optimize the algebraic contradiction. Not fitted to data, but a design choice that sets the constant in the final bound.
  • epsilon = arbitrary positive; tends to 0 as k grows
    Asymptotic slack parameter in the main theorem. It is not estimated from data; the proof shows the bound holds for any fixed epsilon when k is large enough.
  • constant 76 in Lemma 12 = 76
    A loose additive constant chosen so the bound (5r/8+76)n covers small r. It is not optimized and does not affect the asymptotic constant.
assumptions (5)
  • standard math Crossing Lemma for multigraphs with multiplicity two (Szekely; Buengener-Kaufmann)
    Used in Theorem 3 and Theorem 19 to bound crossings in the outercopy.
  • standard math Mohar-Poljak eigenvalue bound mc(G) <= (1/4) lambda_max(L) n
    Core of Lemma 12 for the maximum cut of circulant graphs.
  • standard math Mercer's lower bound on the minimum of the Dirichlet kernel
    Used in Lemma 12 to bound the Laplacian eigenvalue.
  • domain assumption Known tight upper bounds for non-homotopic k-planar multigraphs for k<=3 (folklore, [7], [6], [21])
    Used in Lemma 4 to derive bounds for small k.
  • standard math In any bipartite outerplanar graph, the number of internal faces is at most n/2
    Used in Theorem 20; derived in the proof.

how reviews work

0 comments
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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

25 extracted references · 20 canonical work pages

  1. [2]

    In: SoCG

    Aichholzer, O., Obenaus, J., Orthaber, J., Paul, R., Schnider, P., Steiner, R., Taubner, T., Vogtenhuber, B.: Edge partitions of complete geometric graphs. In: SoCG. LIPIcs, vol. 224, pp. 6:1--6:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik (2022)

  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

  3. [11]

    Journal of Combinatorial Theory, Series B 56(1), 9--15 (1992), https://www.sciencedirect.com/science/article/pii/009589569290003G

    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

  4. [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)

  5. [1]

    Ackerman, E.: On topological graphs with at most four crossings per edge. Comput. Geom. 85 (2019)

  6. [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)

  7. [4]

    In: IWOCA

    Antic, T.: Convex-geometric k-planar graphs are convex-geometric (k+1)-quasiplanar. In: IWOCA . Lecture Notes in Computer Science, vol. 14764, pp. 138--150. Springer (2024)

  8. [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
  1. [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)

  2. [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)

  3. [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)

  4. [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)

  5. [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)

  6. [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

  7. [14]

    In: STOC

    Gon c alves, D.: Edge partition of planar sraphs into two outerplanar graphs. In: STOC . pp. 504--512. ACM (2005)

  8. [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

  9. [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...

  10. [17]

    Kokhas, K., Khrabrov, A., Berlov, S., Ivanov, S., Karpov, D., Petrov, F.: Problems of the Saint Petersburg School Olympiad in Mathematics, 2004 (2004)

  11. [18]

    Mercer, I.D.: http://www.idmercer.com/dirichletkernel.pdf

  12. [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

  13. [20]

    Pach, J., T \' o th, G.: Graphs drawn with few crossings per edge. Comb. 17(3), 427--439 (1997)

  14. [21]

    Sone, K., Suzuki, Y.: Optimal 1-planar multigraphs. Discret. Math. 346(10), 113553 (2023)

  15. [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)

  16. [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...

  17. [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...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.