Pith. sign in

REVIEW 4 major objections 5 minor 28 references

On the 2-colored crossing number

T0 review · 4 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read The rectilinear 2-colored crossing number of $K_n$ grows like a constant times $\binom{n}{4}$, and that constant is at least $1/33$ and at most $0.11798016$.

desk verdict The paper's new duplication mechanism and ratio theorem are genuinely useful, but Theorem 2's upper bound rests on unstated hypotheses about the 135-vertex seed; the gap looks repairable, so the paper deserves a serious referee but with a major-revision request. read the letter →

arxiv 1908.06461 v2 pith:7EQ5MGO5 submitted 2019-08-18 cs.CG math.CO

Oswin Aichholzer , Ruy Fabila-Monroy , Adrian Fuchs , Carlos Hidalgo-Toscano , Irene Parada , Birgit Vogtenhuber , Francisco Zaragoza This is my paper · ORCID
classification cs.CGmath.CO MSC 05C1005C62
keywords 2-coloredcrossingnumberrectilinearcompletegraphstraight-linedrawinghalvingmatchingedgecoloringordertypespositive-fractionErdős–Szekerestheorem
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 studies the best way to color the edges of a straight-line drawing of the complete graph $K_n$ with two colors so that few crossings occur between edges of the same color. It establishes that the asymptotic rate of the unavoidable number of monochromatic crossings is a constant $\mathrm{cr}_2$, and confines that constant to the interval $[1/33,\ 0.11798016]$. The upper bound is reached by a duplication process: starting from a carefully computed 135-vertex drawing, each vertex is replaced by a nearby pair of clones, and the monochromatic-crossing count is tracked through the recursion. The paper also shows that in every sufficiently large straight-line drawing of $K_n$, an optimal 2-coloring leaves strictly less than half of the crossings monochromatic, improving the trivial random-coloring bound of $1/2$. These results pin down the asymptotic cost of using two colors to separate crossings in complete geometric graphs, and they separate the rectilinear 2-colored crossing number from the biplanar crossing number at $K_9$.

What carries the argument

The central object is the $\chi$-halving matching. For a 2-coloring $\chi$ of the edges of a straight-line drawing on a point set $P$, a $\chi$-halving edge at $p$ is an incident edge whose line splits the larger color class at $p$ evenly, meaning the numbers of larger-color edges on the two sides differ by at most one; a $\chi$-halving matching pairs every point with such an edge. The duplication process replaces each point $p$ by two nearby clones $p_1,p_2$ on the line of its matching edge. A six-case color assignment for the new clone–clone edge preserves the halving property in every case except Case 5, where the two clones fall into Cases 2 and 4. Iterating $k$ times gives a drawing of $K_{2^k m}$ whose monochromatic crossing count satisfies the exact recurrence $\mathrm{cr}_2(Q_k,\chi_k) = A 2^{4k} + B 2^{3k} + C 2^{2k} + D 2^k$; the leading coefficient $A$, divided by $m^4$ and scaled by $24$, is the asymptotic upper-bound constant. For the ratio theorem, the key ingredient is the positive-fraction Erdős–Szekeres theorem, which guarantees large subsets $Y_1,Y_2,Y_3,Y_4$ of vertices such that every transversal is a convex quadrilateral; crossing pairs from opposite parts can be colored oppositely so that at most a third of their crossings are monochromatic.

What would settle it

Inspect the published 135-vertex seed configuration, its 2-coloring, and its halving matching, and check whether any vertex has its matched edge in the larger color class with equal numbers of larger-color edges on both sides (the paper's Case 5). If such a vertex exists, the recurrence used for Theorem 2 is not the one proved, and the stated upper-bound constant is not justified by the supplied proof; if no such vertex exists, the gap is closed and the claimed constant stands.

Watch

Extended reading notes

Core claim

For the rectilinear 2-colored crossing number of $K_n$, the paper's central claim is the existence of a limiting constant $\mathrm{cr}_2 = \lim_{n\to\infty} \mathrm{cr}_2(K_n)/\binom{n}{4}$ with $\mathrm{cr}_2(K_n) = \mathrm{cr}_2\binom{n}{4} + \Theta(n^3)$, together with the bounds $\frac{1}{33} \le \mathrm{cr}_2 \le \frac{182873519}{1550036250} < 0.11798016$. The lower bound comes from exhaustive computation over all order types up to size 11, yielding $\mathrm{cr}_2(K_9)=2$, $\mathrm{cr}_2(K_{10})=5$, and $\mathrm{cr}_2(K_{11})=10$, combined with a subset-counting lemma that amplifies a fixed-size bound to all $n$. The upper bound comes from a 135-vertex 2-edge-colored straight-line drawing with 1,470,756 monochromatic crossings and an associated $\chi$-halving matching, fed into a doubling process that yields the closed form $A\cdot 2^{4k} + B\cdot 2^{3k} + C\cdot 2^{2k} + D\cdot 2^k$ for the $k$-th iterate. In addition, for every straight-line drawing $D$ of $K_n$ with $n$ sufficiently large, the paper proves $\mathrm{cr}_2(D)/\mathrm{cr}(D) < 1/2 - c$ for a positive absolute constant $c$, using the positive-fraction Erdős–Szekeres theorem to find large subsets whose crossing structure can be colored with a constant fraction of savings.

Load-bearing premise

The load-bearing premise is that the starting 135-vertex colored drawing has no vertex whose matched halving edge lies in the larger color class while that larger class is split exactly evenly to the left and right of the edge (the paper's Case 5); Theorem 1 is proved only under that assumption, the assumption is not part of the theorem statement, and the paper does not verify it for the seed configuration it uses in Theorem 2.

Editorial extensions

If this is right

  • Because $\mathrm{cr}_2(K_n)$ is asymptotic to $\mathrm{cr}_2 \binom{n}{4}$, the 2-colored crossing number has the same quartic order of growth as the uncolored crossing number; the paper's bounds put the constant between $0.03030$ and $0.11798$.
  • Combined with the known lower bound $277/729$ for the uncolored rectilinear crossing constant, the upper bound gives $\mathrm{cr}_2/\mathrm{cr} \le 0.3105$, so an optimal 2-coloring of a well-drawn $K_n$ wastes less than a third of its crossings on same-color pairs.
  • For any fixed straight-line drawing of $K_n$ with $n$ large, the optimal 2-coloring keeps fewer than $1/2 - c$ of all crossings monochromatic for an absolute $c>0$; the trivial $1/2$ bound from random coloring is uniformly improved.
  • The exact value $\mathrm{cr}_2(K_9)=2$ and the biplanar crossing number of $K_9$ being $1$ separate the rectilinear 2-colored crossing number from the biplanar crossing number.
  • The lower-bound amplification lemma converts any future improvement on a small fixed set into an improved lower bound for all $n$, so the asymptotic lower-bound problem reduces to finitely many small searches.

Reading between the lines

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

  • If the Case 5 condition fails for the published seed, the fix is likely a finite search: because Case 5 is not hereditary only at the initial step, any nearby locally optimized seed that avoids Case 5 would restore the upper-bound proof; the paper does not report such a check.
  • The closed-form duplication constants depend on the full left/right color-class counts at every vertex, so a good upper-bound seed should be selected for balanced color-class splits and small $\mathrm{cr}_2$ simultaneously; the paper indicates this dependence but does not turn it into an optimization criterion.
  • The convex-position ratio $3/8$ plus the numerical observation that convex sets are worst among order types of size 10 suggests that convex position may maximize $\mathrm{cr}_2(D)/\mathrm{cr}(D)$ among all order types; checking all order types up to size 11 or 12 would test this conjecture directly.
  • The proof of Theorem 4 probably extends to $k \ge 3$ colors by replacing four-part transversals with $k$-part convex subsets and coloring the parts cyclically; the paper does not state such an extension.
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

4 major / 5 minor

Summary. This paper investigates the rectilinear 2-colored crossing number cr_2(K_n), defined as the minimum number of monochromatic crossings over all straight-line drawings of K_n and all 2-edge-colorings. The main results are: an upper bound cr_2(K_n) ≤ 182873519/1550036250 * C(n,4) + Θ(n^3), obtained from a duplication process seeded with a 135-vertex 2-colored drawing; a lower bound cr_2(K_n) ≥ 1/33 * C(n,4) + Θ(n^3), derived from exact values cr_2(K_10)=5 and cr_2(K_11)=10 computed via ILP over all order types; and a proof that for every sufficiently large straight-line drawing D of K_n, cr_2(D)/cr(D) < 1/2 - c for a positive absolute constant c, via the positive fraction Erdős–Szekeres theorem. The paper also shows that the biplanar crossing number of K_9 is 1 while cr_2(K_9)=2, and analyzes the ratio for convex and double-chain drawings.

Significance. The duplication framework for the 2-colored setting is a natural and potentially influential extension of the classical method for the rectilinear crossing number; the explicit closed-form duplication formula and the use of small seeds to obtain asymptotic constants are valuable ideas. The lower-bound methodology (reducing asymptotics to exact small cases via ILP) and the improvement over the trivial 1/2 ratio for fixed drawings are also of interest. The authors have made their best seed data available online, which supports reproducibility. If the gaps identified below are repaired, the paper would be a solid contribution to crossing-number theory.

major comments (4)
  1. [Section 2, Theorem 1 and its proof] The statement of Theorem 1 assumes only that the starting set P has a χ-halving matching, but the proof uses two additional assumptions that are not stated: |P| is even, and no point of P falls in Case 5. The proof explicitly says 'we assume that P is such that no point of P falls in Case 5 either', and the closed form in Claim 2 (Appendix A.3) sums only over P2, P1∪P3, and P4∪P6, with no Case 5 term. A Case 5 edge (e ∈ L(p) with Ll(p)=Lr(p)) is a valid χ-halving edge, so the stated hypothesis does not exclude this case. As a consequence, Theorem 1 is not proved for all sets satisfying its stated hypotheses.
  2. [Section 2, Theorem 2 and the 135-vertex seed] The seed used for Theorem 2 has n=135 vertices, which is odd. The proof of Theorem 1 relies on |P| even to ensure that L(p) is strictly larger than S(p) at every vertex; the remark after the proof admits that for odd cardinality the resulting matching may not be χ′-halving. The paper does not verify that the 135-point seed, or the set obtained after one duplication to 270 points, satisfies the hypotheses needed to iterate Claim 2 (even parity, no Case 5, existence of a χ′-halving matching at each step). Therefore the numerical upper bound cr2 ≤ 182873519/1550036250 is not justified by the proof as written.
  3. [Section 4, proof of Theorem 4] In the final paragraph of the proof, the paper asserts '|C2| = ∑_{i=1}^m |E_i|', but E_i was previously introduced as the edge set of the drawing D_i, not as a set of crossings; the equality is unexplained and appears false. The subsequent bound '|E_i| ≥ c_4^4(1−4c_4)^{4i} n^4' is also dimensionally inconsistent, since |E_i| counts edges and the lower bound is of order n^4. The lower bound on |C2| is load-bearing for the conclusion cr2(D)/cr(D) < 1/2 − c. This counting step needs a corrected argument.
  4. [Section 3, lower bound and exact small cases] The exact values cr2(K10)=5 and cr2(K11)=10, which yield the lower bound cr2 ≥ 1/33, are asserted with only a reference to a Master's thesis and an order-type database. Since these values are used as a central result, the paper should provide sufficient detail to make the computation reproducible, for example by including the ILP certificates or a precise description of the ILP and the exhaustive order-type verification for n=10 and n=11.
minor comments (5)
  1. [Section 4] In the sentence 'We color the edges of Fi with the same color and the edges of F′i−1 with the other color', the subscript 'i−1' appears to be a typo and should likely read 'F′i'.
  2. [Appendix A.3, Case 2] In the induction hypothesis for Case 2, the displayed tuple contains the expression '2jSr(p) + 2j−i', which mixes subscripts inconsistently; it should be a single consistent formula such as '2iSr(p) + 2i−1'.
  3. [Theorem 3] The theorem title contains a typo: 'F raction' should be 'Fraction' in 'Positive Fraction Erdős–Szekeres theorem'.
  4. [Theorem 4] The expression 'c4^4⌊|Xi|⌋^4/2' is typeset ambiguously; please ensure that the exponent on c4 and the floor brackets are clear.
  5. [Footnote 5] The data URL is helpful, but a versioned repository or DOI would make the computational results more durable and easier to cite.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; bounds are constructive from explicit seeds and known theorems. Theorem 1–2 have an unstated Case 5 / even-m hypothesis, but that is a proof gap, not circularity.

full rationale

The central derivation is self-contained. Theorem 1 is proved by an explicit duplication case analysis (Section 2, with details in Appendix A): for any seed satisfying its hypotheses, cr2(Q_k, chi_k) is summed by crossing types (Type I/II/III) and reduced to A*24^k + B*23^k + C*22^k + D*2^k, with the coefficients depending on the seed's local color counts, not on the target constant. Theorem 2 then plugs an explicit 135-vertex drawing and 2-coloring (with data published online) into that closed form; this is a constructive upper bound, not a fitted parameter renamed as a prediction. The lower bound cr2 >= 1/33 follows from Lemma 1 and exhaustive determination of cr2(K_11) over all order types up to 11, an external computation. Section 4 uses the Positive Fraction Erdős–Szekeres theorem of Bárány and Valtr, independent of the authors' prior work. Self-citations such as [7] are used as background for heuristics and for the uncolored crossing-constant value; the 2-colored duplication machinery is proved in the paper, so no load-bearing self-citation chain forces the result. The notable caveat is not circular but a correctness gap: Theorem 1's proof assumes m is even ('where m is even') and later states 'we assume that P is such that no point of P falls in Case 5 either', though neither condition appears in Theorem 1's statement or is verified for the 135-vertex seed used in Theorem 2 (m=135 is odd, and Case 5 is not ruled out). The appendix's closed-form sums have no Case 5 term, and the paper's own remark admits that odd-cardinality seeds may fail to produce a chi'-halving matching. This would need repair for the constant to be fully justified, but it is an incomplete hypothesis check, not an equation reducing to its own input.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No numerical parameters are fitted to the target bound; the constants in the theorems are computed from concrete finite witnesses or derived from known external theorems. The assumptions are the existence and correctness of the computational artifacts (135-point seed, ILP exact values) and standard external results.

assumptions (4)
  • standard math The limit lim_{n→∞} cr2(K_n)/C(n,4) exists and is positive.
    Invoked to define the rectilinear 2-colored crossing constant; the paper says the proof follows the uncolored case [24].
  • ad hoc to paper The 135-vertex point set, coloring, and χ-halving matching available at the stated URL have the claimed properties.
    The upper bound of Theorem 2 is computed from this specific seed; its existence is only asserted with a download link, not proven in the text.
  • ad hoc to paper The exhaustive ILP computations over all order types up to size 11 correctly determine cr2(K10)=5 and cr2(K11)=10.
    The lower bound 1/33 depends on cr2(K11)=10; details are in [17] and not in the paper.
  • standard math The Positive Fraction Erdős-Szekeres theorem and the crossing lemma are valid.
    Used in Theorem 4 and Section 3 respectively.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the 2-colored crossing number." pith.science (2026). https://pith.science/paper/7EQ5MGO5

@misc{pith2026190806461,
  author       = {Pith},
  title        = {Pith review of: On the 2-colored crossing number},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7EQ5MGO5}},
  note         = {Machine review of arXiv:1908.06461}
}
abstract

Let $D$ be a straight-line drawing of a graph. The rectilinear 2-colored crossing number of $D$ is the minimum number of crossings between edges of the same color, taken over all possible 2-colorings of the edges of $D$. First, we show lower and upper bounds on the rectilinear 2-colored crossing number for the complete graph $K_n$. To obtain this result, we prove that asymptotic bounds can be derived from optimal and near-optimal instances with few vertices. We obtain such instances using a combination of heuristics and integer programming. Second, for any fixed drawing of $K_n$, we improve the bound on the ratio between its rectilinear 2-colored crossing number and its rectilinear crossing number.

Figures

Figures reproduced from arXiv: 1908.06461 by the authors.

Figure 1
Figure 1. The cases in the duplication process of Theorem 1 when the larger color class at p is blue. The dotted lines represent the lines spanned by the χ-halving matching edges for P. The numbers of blue (red) edges at p to the left and right of le, is denoted with Ll and Lr (Sl and Sr), respectively. Claim 1 The pair (Q, χ0 ) satisfies cr2(Q, χ0 ) = 16 cr2(P, χ) +  m 2  − m + 4X p Ll(p) 2  +  Lr(p) 2  +  Sl(p) 2  … view at source ↗
Figure 2
Figure 2. Left: a 2-colored rectilinear drawing of K8 without monochromatic crossings. Right: a 2-colored drawing of K9 with only one monochromatic (red) crossing. To prove that the heuristics indeed found the best colorings we consider the intersection graph for each drawing D. In the intersection graph every edge in D is a vertex, and two vertices are connected if their edges in D cross. Note that each odd cycle in the inte… view at source ↗
Figure 3
Figure 3. Counting the crossings of different types in the duplication process. A.3 Proof of Claim 2 Claim 2 After k iterations of the duplication process, the following holds cr2(Qk, χk) = A · 2 4k + B · 2 3k + C · 2 2k + D · 2 k where A, B, C and D are rational numbers that depend on P and its χ-halving matching. Proof. Let p be a point of P. We iteratively construct a rooted binary tree T(p) of height k containing a vertex… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 21 canonical work pages

  1. [1]

    In: Proc

    ´Abrego, B.M., Aichholzer, O., Fern´ andez-Merchant, S., Hackl, T., Pammer, J., Pilz, A., Ramos, P., Salazar, G., Vogtenhuber, B.: All good drawings of small complete graphs. In: Proc. 31st European Workshop on Computational Geometry (EuroCG ’15). pp. 57–60 (2015)

    work page 2015

  2. [2]

    Discrete & Computational Geometry 49(4), 747–777 (2013)

    ´Abrego, B.M., Aichholzer, O., Fern´ andez-Merchant, S., Ramos, P., Salazar, G.: The 2-page crossing number of Kn. Discrete & Computational Geometry 49(4), 747–777 (2013). https://doi.org/10.1007/s00454-013-9514-0

    work page doi:10.1007/s00454-013-9514-0 2013

  3. [3]

    Journal of Combinatorial Theory, Series A 114(2), 373–379 (2007)

    ´Abrego, B.M., Fern´ andez-Merchant, S.: Geometric drawings of Kn with few crossings. Journal of Combinatorial Theory, Series A 114(2), 373–379 (2007). https://doi.org/10.1016/j.jcta.2006.05.003

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

  4. [4]

    Electronic Notes in Discrete Mathematics 30, 273–278 (2008)

    ´Abrego, B.M., Fern´ andez-Merchant, S., Lea˜ nos, J., Salazar, G.: A cen- tral approach to bound the number of crossings in a generalized con- figuration. Electronic Notes in Discrete Mathematics 30, 273–278 (2008). https://doi.org/10.1016/j.endm.2008.01.047

    work page doi:10.1016/j.endm.2008.01.047 2008

  5. [5]

    ArXiv e-Prints (2013), https://arxiv.org/abs/1509.01932

    Ackerman, E.: On topological graphs with at most four crossings per edge. ArXiv e-Prints (2013), https://arxiv.org/abs/1509.01932

    arXiv 2013

  6. [6]

    Aichholzer, O.: The order type data base, http://www.ist.tugraz.at/aichholzer/ research/rp/triangulations/ordertypes/, retreived: Oct. 1, 2018

    work page 2018

  7. [7]

    ArXiv e-Prints (2018), https://arxiv.org/abs/1907.07796

    Aichholzer, O., Duque, F., Garc´ ıa-Quintero, O.E., Fabila-Monroy, R., Hidalgo- Toscano, C.: An ongoing project to improve the rectilinear and pseudolinear cross- ing constants. ArXiv e-Prints (2018), https://arxiv.org/abs/1907.07796

    arXiv 2018

  8. [8]

    Computational Geometry: Theory and Applications 36(1), 2–15 (2006)

    Aichholzer, O., Krasser, H.: Abstract order type extension and new results on the rectilinear crossing number. Computational Geometry: Theory and Applications 36(1), 2–15 (2006)

    work page 2006

Show all 28 references
  1. [9]

    In: Proc

    Aichholzer, O., Mulzer, W., Schnider, P., Vogtenhuber, B.: NP-completeness of max-cut for segment intersection graphs. In: Proc. 34th European Workshop on Computational Geometry (EuroCG ’18). pp. 1–6 (2018)

    2018

  2. [10]

    In: Proc

    Aichholzer, O., Orden, D., Ramos, P.: On the structure of sets attaining the rec- tilinear crossing number. In: Proc. 22nd European Workshop on Computational Geometry (EuroCG ’06). pp. 43–46 (2006)

    2006

  3. [11]

    Discrete & Com- putational Geometry 19(3), 335–342 (1998)

    B´ ar´ any, I., Valtr, P.: A positive fraction Erd˝ os-Szekeres theorem. Discrete & Com- putational Geometry 19(3), 335–342 (1998). https://doi.org/10.1007/PL00009350

    1998 doi

  4. [12]

    Bulletin of The American Mathematical Society68 (1962)

    Battle, J., Harary, F., Kodama, Y.: Every planar graph with nine points has a nonplanar complement. Bulletin of The American Mathematical Society68 (1962). https://doi.org/10.1090/S0002-9904-1962-10850-7

    1962 doi

  5. [13]

    Czabarka, ´E., S´ ykora, O., Sz´ ekely, L.A., Vrt’o, I.: Biplanar crossing numbers I: a survey of results and problems, pp. 57–77. Springer Berlin Heidelberg (2006)

    2006

  6. [14]

    Comparing crossing numbers and biplanar crossing numbers using the probabilistic method

    Czabarka, E., S´ ykora, O., Sz´ ekely, L.A., Vrt’o, I.: Biplanar crossing num- bers II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method. Random Structures & Algorithms 33(4), 480–496 (2008). https://doi.org/10.1002/rsa.20221

    2008 doi

  7. [15]

    ACM Comput

    Didimo, W., Liotta, G., Montecchiani, F.: A survey on graph draw- ing beyond planarity. ACM Comput. Surv. 52(1), 4:1–4:37 (2019). https://doi.org/10.1145/3301281

    2019 doi

  8. [16]

    Journal of Graph Algorithms and Applications 18(3), 393–399 (2014)

    Fabila-Monroy, R., L´ opez, J.: Computational search of small point sets with small rectilinear crossing number. Journal of Graph Algorithms and Applications 18(3), 393–399 (2014). https://doi.org/10.7155/jgaa.00328 14 O. Aichholzer et al

    2014 doi

  9. [17]

    Master’s thesis, University of Technology Graz, Austria (2019)

    Fuchs, A.: On the number of monochromatic crossings in rectilinear embeddings of complete graphs. Master’s thesis, University of Technology Graz, Austria (2019)

    2019

  10. [18]

    SIAM Journal on Algebraic and Discrete Methods 4(3), 312–316 (1983)

    Garey, M., Johnson, D.S.: Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods 4(3), 312–316 (1983)

    1983

  11. [19]

    Journal of Graph Theory 84(3), 297–310 (2016)

    Hern´ andez-V´ elez, C., Lea˜ nos, J., Salazar, G.: On the pseudolinear crossing number. Journal of Graph Theory 84(3), 297–310 (2016)

    2016

  12. [20]

    Dagstuhl Reports 6(11), 35–62 (2017)

    Hong, S.H., Kaufmann, M., Kobourov, S.G., Pach, J.: Beyond-planar graphs: al- gorithmics and combinatorics (Dagstuhl seminar 16452). Dagstuhl Reports 6(11), 35–62 (2017). https://doi.org/10.4230/DagRep.6.11.35

    2017 doi

  13. [21]

    Matouˇ sek, J.: Lectures on discrete geometry, Graduate Texts in Mathematics, vol. 212. Springer-Verlag, New York (2002). https://doi.org/10.1007/978-1-4613- 0039-7

    2002 doi

  14. [22]

    IEEE Transactions on Circuit Theory 18(2), 277–280 (1971)

    Owens, A.: On the biplanar crossing number. IEEE Transactions on Circuit Theory 18(2), 277–280 (1971). https://doi.org/10.1109/TCT.1971.1083266

    1971

  15. [23]

    Computational Geometry 68, 2–6 (2018)

    Pach, J., Sz´ ekely, L.A., T´ oth, C.D., T´ oth, G.: Note on k-planar crossing numbers. Computational Geometry 68, 2–6 (2018). https://doi.org/10.1016/j.comgeo.2017.06.015

    2018 doi

  16. [24]

    The American Mathematical Monthly 104(2), 131–137 (1997)

    Richter, R.B., Thomassen, C.: Relations between crossing numbers of complete and complete bipartite graphs. The American Mathematical Monthly 104(2), 131–137 (1997). https://doi.org/10.1080/00029890.1997.11990611

    1997

  17. [25]

    The Electronic Journal of Combinatorics Dynamic Survey 21 (2013/2017)

    Schaefer, M.: The graph crossing number and its variants: a survey. The Electronic Journal of Combinatorics Dynamic Survey 21 (2013/2017)

    2013

  18. [26]

    Discrete Applied Mathematics 155(9), 1106–1115 (2007)

    Shahrokhi, F., Skora, O., Szkely, L.A., Vrto, I.: On k-planar cross- ing numbers. Discrete Applied Mathematics 155(9), 1106–1115 (2007). https://doi.org/10.1016/j.dam.2005.12.011, advances in Graph Drawing: The 11th International Symposium on Graph Drawing

    2007 doi

  19. [27]

    T´ oth, C.D.: Personal communication

  20. [28]

    Canadian Math- ematical Bulletin 6(3), 319–330 (1963)

    Tutte, W.T.: The non-biplanar character of the complete 9-graph. Canadian Math- ematical Bulletin 6(3), 319–330 (1963). https://doi.org/10.4153/CMB-1963-026-x On the 2-Colored Crossing Number 15 A Omitted Details for the Proof of Theorem 1 A.1 Coloring Cases in the Duplication...

    1963 doi

Pith tools

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