Pith. sign in

REVIEW 2 major objections 6 minor 25 references

On the geometric $k$-colored crossing number of $K_n$

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Every seed drawing with at least three points doubles into an exact four-term crossing formula, yielding record upper bounds on the geometric k-colored crossing constant for k=2,...,10.

desk verdict A solid generalization of the 2-color halving-matching construction that gives real factor-three improvements for k≥3; everything rests on an asserted offset-pair table the referee should make the authors prove. read the letter →

arxiv 2505.18014 v1 pith:TDJ27CA6 submitted 2025-05-23 cs.CG cs.DMmath.CO

Benedikt Hahn , Bettina Klinz , Birgit Vogtenhuber This is my paper · ORCID
classification cs.CGcs.DMmath.CO MSC 05C1005C6268U05
keywords geometrick-coloredcrossingnumbercompletegraphrectilineardoublingconstructionhalvingmatchingMAX-k-CUTasymptoticupperbounds
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

The paper gives a way to build straight-line drawings of arbitrarily large complete graphs with few monochromatic crossings, starting from a small seed drawing. It proves that iterating a vertex-doubling construction for t steps produces an exact crossing count of the form $\alpha$*2^(4t) + $\beta$*2^(3t) + gamma*2^(2t) + delta*2^t, so the asymptotic density of monochromatic crossings depends only on quantities computed from the seed. For k=2 through 10, the authors carry this out on heuristic seed drawings, obtaining the best known upper bounds for the geometric k-colored crossing constant, including cr_2 <= 0.11731412 and cr_3 <= 0.06062466. If correct, these bounds replace the previous book-crossing-based bounds for k>=3 by a factor of about three.

What carries the argument

The machinery is an iterated doubling construction: each vertex is replaced by two nearby children along the line spanned by its matching edge, edges between different parents inherit their parent's color, and each parent makes local choices for the sibling edge color and for the matching edges of its two children. The argument is carried by a recurrence for the numbers S_d^c(p) of incident edges of each color on each side of a matching edge, whose offsets (o1, o2) are restricted to five cases by the table in Appendix B. Closed forms for the sums A, B, and C in Appendix C turn the recurrence into the exact four-term formula of Theorem 2, and the leading coefficient $\alpha$ is computed by summing per-vertex local contributions.

What would settle it

Take the published seed instances [15], enumerate all legal detail choices at every vertex, and compute the resulting offset pairs (o1, o2); finding any legal choice with o2 = 2 or with (o1, o2) = (2, 0) would refute the Appendix B table and break the closed-form coefficient formulas. Independently, re-running the supplied Python script should reproduce the seed crossing counts used in Table 1, such as cr_2(P_2; chi_2) = 1468394 and the reported bound 0.11731412; a mismatch would invalidate the numerical constants.

Watch

Extended reading notes

Core claim

The central claim is that for any seed point set P0 with |P0| >= 3, any k-edge-coloring, any matching, and any legal choice of local details, the doubling construction yields cr_k(P_t; chi_t) = $\alpha$ * 2^(4t) + $\beta$ * 2^(3t) + gamma * 2^(2t) + delta * 2^t, with $\alpha$ > 0, $\beta$ < 0, and $\alpha$ + $\beta$ + gamma + delta equal to the seed's monochromatic crossing count. The asymptotic k-colored crossing constant therefore satisfies cr_k <= 24 $\alpha$ / |P0|^4. Table 1 lists the resulting numerical bounds: cr_2 <= 0.11731412, cr_3 <= 0.06062466, cr_4 <= 0.03572151, and so on down to cr_10 <= 0.00692671, improving on all previous upper bounds for k >= 2.

Load-bearing premise

The whole computation rests on the case analysis in Appendix B: every legal choice of local details must yield one of the five offset pairs, with o2 <= 1 and (o1, o2) = (2, 0) impossible; if any legal choice lies outside that table, the closed formulas and every numerical bound in Table 1 fail.

Editorial extensions

If this is right

  • Any seed with at least three points yields a provable asymptotic upper bound on the k-colored crossing constant, so progress reduces to finding better seeds.
  • For a fixed seed and coloring, the matching minimizing the asymptotic coefficient can be found in polynomial time as a minimum-weight saturating matching in a bipartite graph.
  • The improved bounds supersede the book-crossing-number bound 2/k^2 - 1/k^3 for k=3,...,10 by a factor of about three, and improve the previous best bound for k=2.
  • The construction works for every fixed k, so new seeds for larger k would immediately give the first improved bounds there too.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The exact four-term form suggests the doubling construction behaves like a linear dynamical system with growth factor 16 = 2^4, so the leading coefficient alpha might be expressible directly from per-vertex local data, opening the door to optimizing over colorings as well as matchings.
  • Because matching optimization is polynomial once the coloring is fixed, alternating between MAX-k-CUT coloring heuristics and exact matching optimization is a natural way to search for even stronger seeds beyond the heuristic search reported.
  • The five-case offset table effectively classifies the local behavior of the recurrence, so exhaustively enumerating all legal detail choices on a seed is a cheap computation that would either certify the table for that seed or expose a counterexample.
  • A similar doubling recurrence might improve the uncolored rectilinear crossing constant cr_1 if a one-color analogue of the offset analysis can be made to work.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 6 minor

Summary. The paper introduces a general doubling construction for bounding the geometric k-colored crossing number of complete graphs. Starting from a small k-edge-colored straight-line drawing (a point set with a coloring, a matching, and local "details"), the authors define an iterated subdivision of vertices that yields drawings of K_n for exponentially growing n. Theorem 1 gives an exact recurrence for the number of monochromatic crossings, and Theorem 2 states that after t iterations the crossing count has the form α16^t + β8^t + γ4^t + δ2^t. The asymptotic constant is then bounded by 24α/|P0|^4. The authors compute optimal matchings via a bipartite matching formulation and use heuristic seeds for k=2..10, obtaining improved upper bounds, e.g., cr_2 ≤ 0.11731412 and cr_3 ≤ 0.06062466.

Significance. If the proof is completed, this is a substantial contribution. The construction generalizes the halving-matching technique of [5] to arbitrary k and yields the first improvements over the book-crossing-number upper bounds for k≥3, by a factor of about 3; it also slightly improves the k=2 bound. The theoretical framework is elegant: the crossing counting in Theorem 1 is a careful case analysis, the matching optimization is polynomial-time and provably optimal for a fixed seed, and the method gives explicit formulas for the asymptotic coefficient α. The companion artifact [15] supports reproducibility. The main weakness is a missing proof of the offset classification that the closed-form formulas and all numerical bounds depend on.

major comments (2)
  1. [Section 3 (paragraph after Eq. (5))] The classification of offset pairs (o1,o2) into the five entries of the table is asserted but not proved. The text claims "o2 ≤ 1" and "if o1 = 2, then o2 ≠ 0 as is apparent from a short case distinction," but no case distinction is provided. Appendix B proves Lemma 1, which only derives closed forms for given o1,o2; it does not establish the restriction of the offsets to the five allowed pairs. Since the closed forms for B(o1,o2) and C(o1,o2) in Appendix C are given only for those five pairs, and the formula for α in Theorem 2 depends on summing over exactly these pairs, any missing pair (e.g., (2,0) or o2=2) would invalidate the asymptotic coefficient and all numerical bounds in Table 1. This is load-bearing and must be fixed by a rigorous proof of the offset classification.
  2. [Appendix C] The closed forms for A, B, and C are stated without derivation. The proof of Theorem 2 relies on these formulas, including the sign claims α>0 and β<0. While long computations are often omitted, these formulas directly determine the numerical bounds; the authors should either include the derivation or at least provide a verifiable method (e.g., a computer algebra script) so that the formulas can be checked independently.
minor comments (6)
  1. [Section 3, Eq. (6)] In the displayed formula after Eq. (5), the exponent "16^{t-i-i}" appears; this should be "16^{t-i-1}".
  2. [Abstract and Section 1] The abstract uses the notation \overline{\overline{\text{cr}}}_k(K_n), while the body consistently uses cr_k(K_n); please align the notation.
  3. [Theorem 1, Eq. (5)] The last term in the displayed formula has an unclosed bracket: "[S^ℓ_{c(p)}(p_i^j) + S^r_{c(p)}(p_i^j)" should have a closing bracket.
  4. [Section 3, proof of Theorem 2] The proof states "α>0 and β<0 follow from the signs of the relevant coefficients in the closed formulas when |P0|≥3" without specifying which coefficients; please expand this argument.
  5. [Section 4] The numerical results depend on the external artifact [15]; the paper should describe the verification steps (e.g., how the Python script computes cr_k(P_k;χ_k) and the bound) and provide a version identifier or checksum, so that Table 1 can be independently reproduced.
  6. [Section 4] The heuristic search is described only at a high level; please give concrete parameter settings (e.g., number of iterations, perturbation size, MAX-k-CUT heuristic used) for reproducibility.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the upper bounds come from an explicit iterative construction on explicit seed drawings, and no target constant is fitted or derived from itself.

full rationale

The paper's derivation chain is a constructive upper-bound argument. Theorem 1 expands cr_k(P_t; χ_t) by counting crossing types in one doubling step; Theorem 2 then expresses the result as α2^{4t}+β2^{3t}+γ2^{2t}+δ2^t with α, β, γ, δ determined by closed-form sums over A, B, and C. The bound cr_k ≤ 24α/|P0|^4 follows by taking t→∞ against |P_t| choose 4. No parameter is fitted to the quantity being bounded: the seed drawings and colorings are feasible inputs, and any valid seed yields a valid upper bound, so heuristic optimization of the seed is legitimate rather than circular. The only load-bearing non-explicit step is the five-entry classification of offset pairs (o1,o2) in Section 3, including o2≤1 and (o1,o2)≠(2,0). That claim is asserted with a 'short case distinction' and is not proved in Appendix B, but this is a rigor or correctness gap, not a circular reduction: the table does not define the target constant, and the closed forms are conditional on the offsets. Use of the authors' prior work [5] supplies the k=2 seed instance and halving-matching background, but the present construction, optimal matching computation, and asymptotic analysis are independently derived, and the data artifact [15] is code-reproducible. No equation in the paper reduces to its own input by construction, and no fitted value is renamed as a prediction. Hence no circularity is present.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The central claim rests on explicit seed instances generated by MAX-k-CUT heuristics and point perturbation, the polynomial-time matching computation, and the case analysis of offset pairs in Appendix B. No physical constants are involved; the free parameters are the heuristic seeds and the local detail choices, the latter optimized algorithmically.

free parameters (1)
  • Seed drawing (P_k, chi_k) for each k = cr_2=1468394, cr_3=732746, cr_4=413342, cr_5=264459, cr_6=183248, cr_7=133405, cr_8=99638, cr_9=78269, cr_10=60922
    The derived upper bound equals 24 alpha / |P0|^4 and alpha is computed from the seed drawing. The seeds are produced by heuristic MAX-k-CUT search and point perturbation; the paper does not derive them analytically, so the numerical bounds inherit the seeds' quality and validity.
assumptions (3)
  • standard math Existence of the rectilinear and k-colored crossing constants cr_1 and cr_k as limits of cr(K_n)/C(n,4), proven for cr_1 in [20] and with an identical proof for k >= 2.
    Used to state the target constant; not load-bearing for the upper-bound construction itself.
  • domain assumption The seed drawings (P_k, chi_k) listed in the external data artifact [15] are valid straight-line k-colored drawings and the reported cr_k(P_k; chi_k) counts equal the table values.
    The table bounds are computed from these seeds; errors in the artifact would invalidate the numerical upper bounds.
  • ad hoc to paper For every legal choice of details, the offset pairs (o1,o2) for descendants' side counts are restricted to the five entries of the table in Appendix B, with (2,0) impossible and o2 <= 1.
    The closed forms for S^d_c(p_i^j) and hence Theorem 2 rest on this case structure; the proof is only sketched by a short case distinction.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the geometric $k$-colored crossing number of $K_n$." pith.science (2026). https://pith.science/paper/TDJ27CA6

@misc{pith2026250518014,
  author       = {Pith},
  title        = {Pith review of: On the geometric $k$-colored crossing number of $K_n$},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/TDJ27CA6}},
  note         = {Machine review of arXiv:2505.18014}
}
abstract

We study the \emph{geometric $k$-colored crossing number} of complete graphs $\overline{\overline{\text{cr}}}_k(K_n)$, which is the smallest number of monochromatic crossings in any $k$-edge colored straight-line drawing of $K_n$. We substantially improve asymptotic upper bounds on $\overline{\overline{\text{cr}}}_k(K_n)$ for $k=2,\ldots, 10$ by developing a procedure for general $k$ that derives $k$-edge colored drawings of $K_n$ for arbitrarily large $n$ from initial drawings with a low number of monochromatic crossings. We obtain the latter by heuristic search, employing a \textsc{MAX-$k$-CUT}-formulation of a subproblem in the process.

Figures

Figures reproduced from arXiv: 2505.18014 by the authors.

Figure 1
Figure 1. One step in the doubling procedure at a vertex [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. We count crossings based on these three types (I, II, and III). [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 2
Figure 2. The four cases we use to count the number of crossings after one step of the doubling construction. [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 16 canonical work pages

  1. [5]

    On the 2-Colored Crossing Number

    Oswin Aichholzer, Ruy Fabila-Monroy, Adrian Fuchs, Carlos Hidalgo-Toscano, Irene Parada, Birgit Vogtenhuber, and Francisco Zaragoza. “On the 2-Colored Crossing Number”. In: Graph Drawing and Network Visualization . Ed. by Daniel Archambault and Csaba D. T´ oth. Vol. 11904. Cham: Springer International Publishing, 2019, pp. 87–100. doi: 10.1007/978-3-030-35802-0_7

    work page doi:10.1007/978-3-030-35802-0_7 2019

  2. [15]

    Instances with Low Geometric k-Colored Crossing Number

    Benedikt Hahn, Bettina Klinz, and Birgit Vogtenhuber. Instances with Low Geometric k-Colored Crossing Number. 2025. doi: 10.3217/tw2dv-87653

    work page doi:10.3217/tw2dv-87653 2025

  3. [1]

    On ≤ k-Edges, Crossings, and Halving Lines of Geometric Drawings of Kn

    Bernardo M. ´Abrego, Mario Cetina, Silvia Fern´ andez-Merchant, Jes´ us Lea˜ nos, and Gelasio Salazar. “On ≤ k-Edges, Crossings, and Halving Lines of Geometric Drawings of Kn”. In: Computing Research Repository - CORR 48 (2011). doi: 10.1007/s00454-012-9403-y

    work page doi:10.1007/s00454-012-9403-y 2011

  4. [2]

    Geometric Drawings ofKn with Few Crossings

    Bernardo M. ´Abrego and Silvia Fern´ andez-Merchant. “Geometric Drawings ofKn with Few Crossings”. In: Journal of Combinatorial Theory, Series A 114.2 (2007), pp. 373–379. doi: 10.1016/j.jcta.2006. 05.003

    work page doi:10.1016/j.jcta.2006 2007

  5. [3]

    On Topological Graphs with at Most Four Crossings per Edge

    Eyal Ackerman. “On Topological Graphs with at Most Four Crossings per Edge”. In: Computational Geometry 85 (2019), p. 101574. doi: 10.1016/j.comgeo.2019.101574

    arXiv 2019

  6. [4]

    An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants

    Oswin Aichholzer, Frank Duque, Ruy Fabila-Monroy, Oscar Garc ´ ıa-Quintero, and Carlos Hidalgo- Toscano. “An Ongoing Project to Improve the Rectilinear and the Pseudolinear Crossing Constants”. In: Journal of Graph Algorithms and Applications 24.3 (2020). arXiv Version: https://arxiv.org/ abs/1907.07796, pp. 421–432. doi: 10.7155/jgaa.00540

    work page Pith review arXiv 2020

  7. [6]

    New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of Kn

    Oswin Aichholzer, Jesus Garcia, David Orden, and Pedro Ramos. “New Lower Bounds for the Number of (≤ k)-Edges and the Rectilinear Crossing Number of Kn”. In: Discrete & Computational Geometry 38.1 (2007), pp. 1–14. doi: 10.1007/s00454-007-1325-8

    work page doi:10.1007/s00454-007-1325-8 2007

  8. [7]

    Polynomial Time Approximation Schemes for Dense Instances of N P-Hard Problems

    Sanjeev Arora, David Karger, and Marek Karpinski. “Polynomial Time Approximation Schemes for Dense Instances of N P-Hard Problems”. In: Journal of Computer and System Sciences 58.1 (1999), pp. 193–210. doi: 10.1006/jcss.1998.1605

    arXiv 1999

Show all 25 references
  1. [8]

    Some Provably Hard Crossing Number Problems

    Daniel Bienstock. “Some Provably Hard Crossing Number Problems”. In: Discrete & Computational Geometry 6.3 (1991), pp. 443–459. doi: 10.1007/BF02574701. 6

    1991 doi

  2. [9]

    A Note on the 2-Colored Rectilinear Crossing Number of Random Point Sets in the Unit Square

    Sergio Cabello, ´Eva Czabarka, Ruy Fabila-Monroy, Yuya Higashikawa, Raimund Seidel, L´ aszl´ o Sz´ ekely, Josef Tkadlec, and Alexandra Wesolek. “A Note on the 2-Colored Rectilinear Crossing Number of Random Point Sets in the Unit Square”. In: Acta Mathematica Hungarica 173.1 (...

    2024 doi

  3. [10]

    An Upper Bound to the Crossing Number of the Complete Graph Drawn on the Pages of a Book

    Ernesto Damiani, Ottavio D’Antona, and Payam Salemi. “An Upper Bound to the Crossing Number of the Complete Graph Drawn on the Pages of a Book”. In: Journal of Combinatorics, Information & System Sciences. Vol. 19. 1994, pp. 75–84

    1994

  4. [11]

    Improved Lower Bounds on Book Crossing Numbers of Complete Graphs

    Etienne de Klerk, Dmitrii V. Pasechnik, and Gelasio Salazar. “Improved Lower Bounds on Book Crossing Numbers of Complete Graphs”. In: SIAM Journal on Discrete Mathematics 27.2 (2013), pp. 619–633. doi: 10.1137/120886777

    2013 doi

  5. [12]

    Mathematical Programming Formulation of Rectilinear Crossing Minimization

    Nathaniel Dean. Mathematical Programming Formulation of Rectilinear Crossing Minimization . Tech. rep. 12. DIMACS, 2002

    2002

  6. [13]

    A Note on the k -Colored Crossing Ratio of Dense Geometric Graphs

    Ruy Fabila-Monroy. “A Note on the k -Colored Crossing Ratio of Dense Geometric Graphs”. In: Computational Geometry 124–125 (2025), p. 102123. doi: 10.1016/j.comgeo.2024.102123

    2025

  7. [14]

    Some Simplified NP -Complete Graph Problems

    Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. “Some Simplified NP -Complete Graph Problems”. In: Theoretical Computer Science 1.3 (1976), pp. 237–267. doi: 10.1016/0304- 3975(76)90059-1

    1976 doi

  8. [16]

    On the Hardness of Approximating Max k -Cut and Its Dual

    Viggo Kann, Sanjeev Khanna, Jens Lagergren, and Alessandro Panconesi. “On the Hardness of Approximating Max k -Cut and Its Dual”. In: Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems . IEEE Computer Society, 1996, pp. 61–67

    1996

  9. [17]

    The Hungarian Method for the Assignment Problem

    Harold W. Kuhn. “The Hungarian Method for the Assignment Problem”. In: Naval Research Logistics Quarterly 2.1-2 (1955), pp. 83–97. doi: 10.1002/nav.3800020109

    1955 doi

  10. [18]

    Crossing Minimization in Linear Embeddings of Graphs

    Sumio Masuda, Kazuo Nakajima, Toshinobu Kashiwabara, and Toshio Fujisawa. “Crossing Minimization in Linear Embeddings of Graphs”. In: IEEE Transactions on Computers 39.1 (1990), pp. 124–127. doi: 10.1109/12.46286

    1990 doi

  11. [19]

    Note onk -Planar Crossing Numbers

    J´ anos Pach, L´ aszl´ o A. Sz´ ekely, Csaba D. T´ oth, and G´ eza T´ oth. “Note onk -Planar Crossing Numbers”. In: Computational Geometry . Special Issue in Memory of Ferran Hurtado 68 (2018), pp. 2–6. doi: 10.1016/j.comgeo.2017.06.015

    2018 doi

  12. [20]

    Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs

    R. Bruce Richter and Carsten Thomassen. “Relations Between Crossing Numbers of Complete and Complete Bipartite Graphs”. In: The American Mathematical Monthly 104.2 (1997), pp. 131–137. doi: 10.1080/00029890.1997.11990611

    1997

  13. [21]

    Vilmar Jeft´ e Rodrigues de Sousa.Max-k-Cut Branching Algorithm and Heuristics . 2020. url: https: //github.com/vilmarjet/maxKcut (visited on 03/07/2025)

    2020

  14. [22]

    Computational Study of a Branching Algorithm for the Maximum k -Cut Problem

    Vilmar Jeft´ e Rodrigues de Sousa, Miguel F. Anjos, and S´ ebastien Le Digabel. “Computational Study of a Branching Algorithm for the Maximum k -Cut Problem”. In: Discrete Optimization 44 (2022), p. 100656. doi: 10.1016/j.disopt.2021.100656

    2022

  15. [23]

    The Graph Crossing Number and Its Variants: A Survey

    Marcus Schaefer. “The Graph Crossing Number and Its Variants: A Survey”. In: The Electronic Journal of Combinatorics (2024), DS21. doi: 10.37236/2713

    2024 doi

  16. [24]

    The Book Crossing Number of a Graph

    Farhad Shahrokhi, L´ aszl´ o A. Sz´ ekely, Ondrej S´ ykora, and Imrich Vrt’o. “The Book Crossing Number of a Graph”. In: Journal of Graph Theory 21.4 (1996), pp. 413–424. doi: 10.1002/(SICI)1097- 0118(199604)21:4<413::AID-JGT7>3.0.CO;2-S

    1996 doi

  17. [25]

    On the Biplanar and k-Planar Crossing Numbers

    Alireza Shavali and Hamid Zarrabi-Zadeh. “On the Biplanar and k-Planar Crossing Numbers”. In: Proceedings of the 34th Canadian Conference on Computational Geometry . 2022, pp. 293–297. 7 A Proof of Theorem 1 Theorem 1. Given a point set P0, a k-edge-coloring χ0, a matching m0,...

    2022

Pith tools

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