Pith. sign in

REVIEW 5 minor 25 references

Crossing Numbers of Beyond-Planar Graphs

T0 review · 0 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 For 1-planar, quasi-planar, and fan-planar graphs, forbidding certain local crossing patterns can force a linear number of crossings even when a constant number would suffice.

desk verdict A clean set of constructions showing that restricted crossing numbers can exceed the unrestricted one by a linear factor, with a tight 1-planar bound. read the letter →

arxiv 1908.03153 v2 pith:52VRXX4W submitted 2019-08-08 cs.CG cs.DM

Markus Chimani , Philipp Kindermann , Fabrizio Montecchiani , Pavel Valtr This is my paper · ORCID
classification cs.CGcs.DM MSC 05C1068R10
keywords crossingnumberbeyond-planargraphs1-planarquasi-planarfan-planarratiographdrawing
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 asks whether forbidding local edge-crossing patterns - such as an edge being crossed twice, three mutually crossing edges, or fan patterns - can force far more crossings than are strictly necessary. It answers yes for three prominent classes of beyond-planar graphs. For 1-planar graphs the effect is maximal: for every $\ell \ge 7$ there is a graph $G_\ell$ on $n = 11\ell+2$ vertices whose every 1-planar drawing has $n-2$ crossings, while the same graph can be drawn with only 2 crossings. For quasi-planar and fan-planar graphs the paper constructs $n$-vertex examples where any drawing respecting the local rule has at least a linear number of crossings, yet 3 crossings (or fewer) suffice without the rule. The results show that the visual restriction itself, not the graph's intrinsic complexity, is what forces the large crossing count.

What carries the argument

The central objects are three rigid constructions, each built to make a prohibited crossing pattern astronomically costly. For 1-planar graphs, the construction uses a graph $P$ (a medial extension of the Cartesian product of a length-2 path and a length-$\ell$ cycle) whose only 1-planar embedding on the sphere is planar. The graph $G_\ell$ adds $P$'s planar dual $P^*$, binding edges that force the dual vertex $f^*$ to lie in the large polar face $f$ of $P$, and a special edge $(x,y^*)$ that is crossed at least twice in the planar embedding but can be drawn crossing-free in the unique non-planar 1-planar embedding, where every edge of $P$ crosses every edge of $P^*$ once. For quasi-planar and fan-planar bounds, the mechanism is an 'extended edge': two independent edges whose endpoints are joined by $\ell-1$ internally disjoint length-2 paths. Lemma 5 shows that if the two base edges cross, then at least $\ell$ crossings must occur; the constructions then force either such a crossing or, through a separating curve, a bundle of paths crossing a special edge. The fan-planar variant instead packs $\ell$ subdivisions of $K_{3,3}$ that all share one edge, so each requires a distinct crossing, and fan-planarity rules out the only draw that could merge two crossings.

What would settle it

For $\ell = 7$ in Theorem 1, the graph $G_7$ has $n = 79$ vertices; the theorem predicts $\mathrm{cr}_{1\text{-}\mathrm{pl}}(G_7) = 77$ and $\mathrm{cr}(G_7) = 2$. Drawing $G_7$ in any 1-planar way with fewer than 77 crossings, or finding an unrestricted drawing with only 1 crossing, would refute the claimed tight ratio. More directly, locating a second 1-planar embedding of the rigid graph $H_7$ on the sphere would break the rigidity premise and the entire lower-bound argument.

Watch

Extended reading notes

Core claim

Formally, the paper proves three separation theorems. Theorem 1: for every $\ell \ge 7$ the 1-planar graph $G_\ell$ with $n = 11\ell+2$ vertices satisfies $\mathrm{cr}_{1\text{-}\mathrm{pl}}(G_\ell) = n - 2$ and $\mathrm{cr}(G_\ell) = 2$, making the ratio exactly $n/2 - 1$, the largest possible because any 1-planar drawing of an $n$-vertex graph has at most $n-2$ crossings. Theorem 4: for every $\ell \ge 2$ a quasi-planar graph with $n = 12\ell - 5$ vertices has quasi-planar crossing number at least $\ell$ and unrestricted crossing number at most 3, giving ratio $\Omega(n)$; the proof extends to $k$-quasi-planar graphs with ratio $\Omega(n/k^3)$ (Corollary 6). Theorem 7: for every $\ell \ge 2$ a fan-planar graph with $n = 9\ell + 1$ vertices has fan-planar crossing number exactly $\ell$ and unrestricted crossing number 3, again giving ratio $\Omega(n)$. Corollary 3 generalizes the 1-planar bound to $k$-planar multigraphs with ratio at least $k(n-2)/2$.

Load-bearing premise

The 1-planar ratio bound rests on the rigidity premise that the graph $H_\ell$ (and hence the built $P$) has exactly one 1-planar embedding on the sphere; if another embedding existed, the binding and special edges might be drawable without forcing the dual into the polar faces, and the $n-2$ lower bound could collapse.

Editorial extensions

If this is right

  • For 1-planar graphs the crossing ratio is exactly $n/2 - 1$: no 1-planar family can force a larger gap between the best 1-planar and best unrestricted drawing.
  • For $k$-planar multigraphs the ratio is at least $k(n-2)/2$, so allowing more crossings per edge widens the forced gap (Corollary 3).
  • For quasi-planar graphs the ratio is $\Omega(n)$ even when the unrestricted crossing number is at most 3, and for $k$-quasi-planar graphs it is $\Omega(n/k^3)$ (Theorem 4, Corollary 6).
  • For fan-planar graphs the ratio is $\Omega(n)$ with unrestricted crossing number exactly 3 (Theorem 7).
  • The constructions provide explicit examples where the local-restriction crossing number exceeds the unrestricted crossing number by an arbitrarily large linear factor, not merely by a constant.

Reading between the lines

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

  • The dual-interleaving template behind Theorem 1 is likely reusable: any rigid graph with a unique embedding and a polar face structure might yield a similar separation when its dual is bound to it, so one could test it on other uniquely-embeddable graph families.
  • The redrawing remark in Appendix B suggests a clean structural lemma: in these extremal examples every bundle of length-two paths can be assumed to run along a single trajectory without increasing crossings. That lemma, if formalized, would simplify future lower-bound proofs for crossing numbers under local pattern restrictions.
  • The paper conjectures that the quasi-planar/fan-planar ratio can reach the quadratic upper bound; if true, even single forbidden local patterns would force a blow-up of the same order as the edge-count maximum, which would sharpen the folklore that restrictions beyond planarity are cheap.
  • One could push the separation further by asking for trade-offs: for each function $f(n)$, how large must the unrestricted crossing number be before the gap between restricted and unrestricted space becomes sublinear? The present constructions only handle constant unrestricted crossing numbers.
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

0 major / 5 minor

Summary. The paper investigates the gap between the ordinary crossing number and the crossing number restricted to three beyond-planar drawing styles: 1-planar, quasi-planar, and fan-planar drawings. It constructs, for each of these classes, n-vertex graphs for which every drawing respecting the local restriction has Ω(n) crossings, while an unrestricted drawing has only O(1) crossings. For 1-planar graphs the authors obtain the tight ratio n/2-1 by a graph G_l with cr_1-pl(G_l)=n-2 and cr(G_l)=2 (Theorem 1), using a rigid graph from Korzhik and Mohar together with its dual and binding edges. For quasi-planar and fan-planar graphs they prove lower bounds of Ω(n) with unrestricted crossing number at most 3 (Theorems 4 and 7), and they extend the quasi-planar construction to k-quasi-planar graphs (Corollary 6). The proofs are based on explicit constructions and a simple counting lemma (Lemma 5), with a lengthy case analysis in Appendix A supporting the 1-planar result.

Significance. The paper answers a natural and timely question in beyond-planar graph drawing: avoiding forbidden crossing patterns can force a linear number of crossings even when a few crossings would suffice without those restrictions. The 1-planar result is tight and therefore completely settles the ratio for that class, while the quasi-planar and fan-planar results give linear lower bounds that are within a linear factor of the trivial upper bound. The main strengths are the explicitness of the constructions, the elementary nature of Lemma 5, and the detailed case analysis in Appendix A. There are no fitted parameters or circular arguments; the only non-self-contained ingredient is the cited Korzhik-Mohar rigidity theorem, which is credible and appears to apply as stated. This is a solid contribution that will be of interest to researchers in graph drawing and crossing numbers.

minor comments (5)
  1. [Section 2, Theorem 1] The equality cr_1-pl(G_l)=n-2 relies on the Korzhik-Mohar rigidity theorem for the graph H_l, but the precise statement of that theorem and the range of l for which it is valid are not given. Since this is the only non-self-contained step in the tightness proof, I recommend stating the theorem explicitly (or at least its exact consequence used here) so that the reader can verify the applicability to the H_l used in the construction.
  2. [Corollary 3] The statement says 'For every l >= 6', but Theorem 1 and the case analysis in Lemma 2 require l >= 7 (for example, the argument uses 'at most 4 < l-2 edges' on the boundary of a face). Please correct the range or explain why the multigraph replacement changes the threshold.
  3. [Corollary 6] The stated vertex count n=2k(l+1)+1 does not match the construction described immediately above it, namely the same construction as Theorem 4 with the cycle length changed to 2k. That construction has 2k+1 vertices in the base graph and 4k(l-1) subdivision vertices, giving n=4kl-2k+1, not 2k(l+1)+1. Please correct the formula (the correct count is 2k(2l-1)+1) or clarify the intended construction.
  4. [Section 3, proof of Theorem 4] The phrase 'the unique face of size 6 in G''' may confuse readers, because G' contains a wheel on seven vertices and has several faces. It should be clarified that the face in question is the face bounded by the (subdivided) 6-cycle after x is placed inside the cycle.
  5. [Appendix A, Lemma 2] The proof of Lemma 2 is intricate and depends heavily on the drawings in Figures 4a-4d. Please ensure that these figures remain legible in the final version and that the captions indicate which part of the case analysis each figure illustrates.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the constructions are explicit and the cited Korzhik–Mohar rigidity theorem is independent external support.

full rationale

The paper's central claims are proved by explicit graph constructions with no fitted parameters and no quantity defined in terms of the target result. The 1-planar lower bound (Theorem 1) relies on the cited rigidity result of Korzhik and Mohar that H_ell has a unique 1-planar embedding; this is an external, independently established theorem used as a hypothesis, not an assertion equivalent to the theorem being proved. The quasi-planar and fan-planar proofs (Theorems 4 and 7) are self-contained, using explicit constructions, Lemma 5, and elementary crossing-count arguments. The crossing-number upper bounds are obtained by explicit drawings. No prediction is merely a renamed input, no parameter is fitted to the data being predicted, and no load-bearing premise is justified solely by a self-citation chain. The self-citations present are to standard surveys and background material, not to results whose validity is assumed in place of proof. Thus the circularity burden is nil.

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

The central claims rest on standard graph theory facts (Euler's formula, drawing conventions, non-planarity of K_3,3 subdivisions) and on the cited Korzhik-Mohar rigidity theorem. No parameters are fitted to data; ℓ and k are size parameters in the constructions, not fitted values. No new entities are postulated.

assumptions (4)
  • domain assumption H_ℓ has exactly one 1-planar embedding on the sphere, and it is crossing-free.
    Invoked in Section 2 to make the graph P rigid, forcing P* into the polar faces in any 1-planar drawing. This is a result from Korzhik and Mohar [16], cited but not proven. If it were false, the lower bound in Theorem 1 would not follow.
  • standard math In a simple drawing, adjacent edges do not cross and non-adjacent edges cross at most once.
    Stated in Notation and Definitions and used throughout to apply Lemma 5 and to count crossings. This is a standard convention for simple drawings.
  • standard math Every subdivision of K_3,3 is non-planar and hence requires at least one crossing in any drawing.
    Used in the proof of Theorem 7 to lower bound cr(G_ℓ) by 3 and to require crossings in fan-planar drawings.
  • standard math Euler's polyhedra formula and the bound of 4n-8 edges for 1-planar graphs imply at most n-2 crossings in a 1-planar drawing.
    Used in Section 2 to show the upper bound cr_1-pl(G) ≤ n-2, against which the construction is tight. Also used to argue cr(G) cannot be 1 when cr_1-pl is large.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Crossing Numbers of Beyond-Planar Graphs." pith.science (2026). https://pith.science/paper/52VRXX4W

@misc{pith2026190803153,
  author       = {Pith},
  title        = {Pith review of: Crossing Numbers of Beyond-Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/52VRXX4W}},
  note         = {Machine review of arXiv:1908.03153}
}
abstract

We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are $n$-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has $\Omega(n)$ crossings, while $O(1)$ crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.

Figures

Figures reproduced from arXiv: 1908.03153 by the authors.

Figure 1
Figure 1. Construction of the graph G` in the proof of Theorem 1. Blue circles and edges are P; red squares and bold edges are P ∗ ; green dashed edges are the binding edges; and the orange very bold edge is the special edge. Let z be a vertex of P on the boundary of f. Let y be the face of size 4 that has z on its boundary. Let x be the degree-6 vertex on the boundary of y. We obtain G` from G0 by adding the special edge (x,… view at source ↗
Figure 2
Figure 2. Illustration for the proof of Theorem 4. [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Illustration for the proof of Theorem 7. [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Proof that P and P ∗ do not cross when g ∗ lies in f. (Left) situation in P ∗ and (Right) proof that the drawing cannot be 1-planar. there is no way to draw the path from w to g ∗ that consists of 4 edges without multiple crossings. Second, assume that v is not adjacen…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 10 canonical work pages

  1. [1]

    Discrete Comput

    Alon, N., Erd¨ os, P.: Disjoint edges in geometric graphs. Discrete Comput. Geom. 4, 287–290 (1989). https://doi.org/10.1007/BF02187731

    work page doi:10.1007/bf02187731 1989

  2. [2]

    In: Proc

    Batini, C., Furlani, L., Nardelli, E.: What is a good diagram? A pragmatic ap- proach. In: Proc. 4th Int. Conf. Entity-Relationship Approach (ER’85). pp. 312– 319 (1985), http://dl.acm.org/citation.cfm?id=647510.726382

    work page arXiv 1985

  3. [3]

    IEEE Trans

    Batini, C., Nardelli, E., Tamassia, R.: A layout algorithm for data flow diagrams. IEEE Trans. Software Eng. 12(4), 538–546 (1986). https://doi.org/10.1109/TSE.1986.6312901

    arXiv 1986

  4. [4]

    Bekos, M.A., Kaufmann, M., Montecchiani, F.: Guest editors’ foreword and overview - Special issue on graph drawing beyond planarity. J. Graph Algorithms Appl. 22(1), 1–10 (2018). https://doi.org/10.7155/jgaa.00459

    work page doi:10.7155/jgaa.00459 2018

  5. [5]

    Discrete Comput

    Bienstock, D.: Some provably hard crossing number problems. Discrete Comput. Geom. 6, 443–459 (1991). https://doi.org/10.1007/BF02574701

    doi:10.1007/bf02574701 1991

  6. [6]

    In: Proc

    Chimani, M., Mutzel, P., Bomze, I.: A new approach to exact crossing minimiza- tion. In: Proc. 16th Europ. Symp. Algorithms (ESA’08). pp. 284–296. No. 5193 in LNCS, Springer (2008). https://doi.org/10.1007/978-3-540-87744-8 24

    doi:10.1007/978-3-540-87744-8 2008

  7. [7]

    Prentice-Hall (1999)

    Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice-Hall (1999)

    1999

  8. [8]

    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 8 M. Chimani et al

    doi:10.1145/3301281 2019

Show all 25 references
  1. [9]

    In: Charikar, M

    Hlinˇ en´ y, P., Chimani, M.: Approximating the crossing number of graphs em- beddable in any orientable surface. In: Charikar, M. (ed.) Proc. 21sth Ann. ACM-SIAM Symp. Discr. Algorithms (SODA’10). pp. 918–927. SIAM (2010). https://doi.org/10.1137/1.9781611973075.74

    2010 doi

  2. [10]

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

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

    2016 doi

  3. [11]

    NII Shonan Meet

    Hong, S., Tokuyama, T.: Algoritihmcs for beyond planar graphs (NII shonan meet- ing 2016-17). NII Shonan Meet. Rep. 2016 (2016), http://shonan.nii.ac.jp/ shonan/report/no-2016-17/

    2016

  4. [12]

    Huang, W., Eades, P., Hong, S.: Larger crossing angles make graphs easier to read. J. Vis. Lang. Comput. 25(4), 452–465 (2014). https://doi.org/10.1016/j.jvlc.2014.03.001

    2014 doi

  5. [13]

    Arxiv Report (2014), http://arxiv.org/abs/1403.6184

    Kaufmann, M., Ueckerdt, T.: The density of fan-planar graphs. Arxiv Report (2014), http://arxiv.org/abs/1403.6184

    2014 arXiv

  6. [14]

    In: Johnson, D.S., Feige, U

    Kawarabayashi, K., Reed, B.A.: Computing crossing number in linear time. In: Johnson, D.S., Feige, U. (eds.) Proc. 39th Ann. ACM Symp. Theory Comput. (STOC’07). pp. 382–390. ACM (2007). https://doi.org/10.1145/1250790.1250848

    2007

  7. [15]

    Kobourov, S.G., Liotta, G., Montecchiani, F.: An annotated bib- liography on 1-planarity. Comput. Sci. Reviews 25, 49–67 (2017). https://doi.org/10.1016/j.cosrev.2017.06.002

    2017 doi

  8. [16]

    Korzhik, V.P., Mohar, B.: Minimal obstructions for 1-immersions and hardness of 1-planarity testing. J. Graph Theory 72(1), 30–71 (2013). https://doi.org/10.1002/jgt.21630

    2013 doi

  9. [17]

    Mutzel, P.: An alternative method to crossing minimization on hi- erarchical graphs. SIAM J. Optimization 11(4), 1065–1080 (2001). https://doi.org/10.1137/S1052623498334013

    2001 doi

  10. [18]

    Combinatorica 17(3), 427–439 (1997)

    Pach, J., T´ oth, G.: Graphs drawn with few crossings per edge. Combinatorica 17(3), 427–439 (1997). https://doi.org/10.1007/BF01215922

    1997 doi

  11. [19]

    Interacting with Computers 13(2), 147–162 (2000)

    Purchase, H.C.: Effective information visualisation: a study of graph drawing aesthetics and algorithms. Interacting with Computers 13(2), 147–162 (2000). https://doi.org/10.1016/S0953-5438(00)00032-1

    2000 doi

  12. [20]

    Empirical Software Engineering 7(3), 233–255 (2002)

    Purchase, H.C., Carrington, D.A., Allder, J.A.: Empirical evaluation of aesthetics- based graph layout. Empirical Software Engineering 7(3), 233–255 (2002)

    2002

  13. [21]

    Schaefer, M.: The graph crossing number and its variants: A survey. Electr. J. Comb. DS21 (2017), https://www.combinatorics.org/ojs/index.php/eljc/ article/view/DS21

    2017

  14. [22]

    IEEE Trans

    Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierar- chical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109–125 (1981). https://doi.org/10.1109/TSMC.1981.4308636

    1981

  15. [23]

    Suk, A., Walczak, B.: New bounds on the maximum number of edges in k-quasi-planar graphs. Comput. Geom. 50, 24–33 (2015). https://doi.org/10.1016/j.comgeo.2015.06.001

    2015 doi

  16. [24]

    ftp://ftp.ifi.savba.sk/ pub/imrich/crobib.pdf (2014)

    Vrt’o, I.: Crossing numbers of graphs: A bibliography. ftp://ftp.ifi.savba.sk/ pub/imrich/crobib.pdf (2014)

    2014

  17. [25]

    parallel

    Ware, C., Purchase, H.C., Colpoys, L., McGill, M.: Cognitive mea- surements of graph aesthetics. Inform. Vis. 1(2), 103–110 (2002). https://doi.org/10.1057/palgrave.ivs.9500013 Crossing Numbers of Beyond-Planar Drawings 9 A Omitted proofs of Section 2 Lemma 2. G′ has only two ...

    2002 doi

Pith tools

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