pith. sign in

arxiv: 2410.00206 · v4 · submitted 2024-09-30 · 💻 cs.CG · math.CO

A Unified FPT Framework for Crossing Number Problems

\'Eric Colin de Verdi\`ere , Petr Hlin\v{e}n\'y This is my paper

Pith reviewed 2026-05-23 20:23 UTC · model grok-4.3

classification 💻 cs.CG math.CO
keywords crossing numberfixed-parameter tractabilitygraph drawingsurfacessimplicial complexestopological drawingsrotation systemsedge-colored graphs
0
0 comments X

The pith

Deciding whether a graph has a drawing in class D on surface S is fixed-parameter tractable in the genus of S and the maximum crossings allowed in D.

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

The paper gives a single algorithmic framework that covers many different versions of the crossing number question at once. It fixes a surface S together with a class D of permitted drawings, assumes that one can test whether a given drawing belongs to D, and assumes D is closed under taking sub-drawings, adding edges without new crossings, and moving the whole picture by a homeomorphism of S. Under those conditions the problem of deciding whether an input graph has a drawing in D, and of producing one, becomes fixed-parameter tractable with the parameter being essentially the genus of S and the largest number of crossings that any drawing in D may contain. The same framework also handles edge-colored graphs, where crossings are distinguished by the colors of the crossed edges, and it permits a bounded number of edge deletions or vertex splits before the drawing step.

Core claim

Under the stated assumptions on the class D of drawings on surface S, there is an FPT algorithm, parameterized by the genus of S and the maximum number of crossings permitted in D, that decides whether an input graph admits a drawing in D and constructs one when it exists. The algorithm works by reducing the question to the embeddability of an auxiliary graph on a two-dimensional simplicial complex whose size is bounded by a function of the parameter. The framework also extends directly to the colored-edge and bounded-modification settings.

What carries the argument

Reduction of the drawing-in-D question to embeddability of an auxiliary graph on a two-dimensional simplicial complex whose complexity depends only on genus and crossing bound.

If this is right

  • Linear or quadratic FPT algorithms exist for numerous specific crossing-number variants already studied in the literature.
  • The same results hold when the drawings are required to lie on any fixed surface.
  • In some variants the rotation system of the drawing can be fixed in advance.
  • Crossings may be distinguished according to the colors of the two edges that cross.
  • A bounded number of edge removals and vertex splits may be performed on the input graph before the drawing step.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same reduction technique could be tried on other topological drawing problems whose constraints are local and closed under the listed operations.
  • Existing algorithms for testing embeddability on simplicial complexes can now be plugged in to obtain concrete runtimes for many crossing-number problems.
  • The framework suggests that the main computational obstacle in these problems is the global topological consistency captured by the simplicial complex rather than the crossing condition itself.
  • One could test whether the same closure properties hold for approximate or list versions of crossing number and thereby obtain FPT results for those variants as well.

Load-bearing premise

That membership in the allowed drawing class D is algorithmically testable and that D stays closed when a drawing is restricted, extended without new crossings, or moved by any homeomorphism of the surface.

What would settle it

A concrete pair consisting of a graph G and a class D satisfying the closure and testability conditions, together with an explicit embedding of the constructed simplicial complex whose corresponding drawing on S lies outside D.

Figures

Figures reproduced from arXiv: 2410.00206 by \'Eric Colin de Verdi\`ere, Petr Hlin\v{e}n\'y.

Figure 3
Figure 3. Figure 3: Let G1 be the colored graph obtained from G by attaching a 4-clique to each vertex v of G, that is, by adding three new vertices making a 4-clique with v. The edges of each attached 4-clique get color c + 1. (This is a new color, and we assume qc+1 = 0.) Let G2 be the uncolored graph obtained from G1 by replacing each edge of color i with a necklace of thickness p + 2q + 2λ(r) + i, where q = P j qj , and b… view at source ↗
read the original abstract

The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework yielding fixed-parameter tractable (FPT) algorithms for many generalized crossing number problems. Our framework takes the following form. We fix a surface S and a class D of "allowed" topological drawings of graphs in S (e.g., some class of drawings with at most t crossings). We assume that testing membership in D can be done algorithmically, and that restricting a drawing in D, extending it without adding any crossing, or transforming it with a self-homeomorphism of S yields a drawing that is also in D. Then deciding whether an input graph G has a drawing in D, and computing one if it is the case, is fixed-parameter tractable in (essentially) the genus of S and the maximum number of crossings in a drawing in D. More generally, we may take as input an edge-colored graph and distinguish crossings by the colors of the involved edges; and we may allow a bounded number of edge removals and vertex splits on G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This implies, in a unified way, linear or quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle's metatheorem, but our algorithms have a better runtime. Moreover, our framework extends to these crossing number variants in any fixed surface, and also allows us to fix the rotation system of the drawing of a graph in some variants.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper develops a unified FPT framework for deciding whether an input graph G admits a drawing in a prescribed class D of topological drawings on a fixed surface S (and computing one if it exists). The framework assumes an algorithmic membership test for D together with closure under restriction, crossing-free extension, and self-homeomorphisms of S; under these hypotheses it reduces the problem to embeddability of a graph on a two-dimensional simplicial complex whose size depends only on genus(S) and the maximum number of crossings permitted by D. The same reduction extends to edge-colored variants, bounded edge deletions, and vertex splits, and yields linear or quadratic FPT algorithms for numerous concrete crossing-number problems previously treated individually (some via Courcelle's theorem). The framework also applies on any fixed surface and permits fixing the rotation system in certain cases.

Significance. If the reduction is correct, the result supplies a single, clean algorithmic meta-theorem that simultaneously recovers and improves the runtime of many existing FPT algorithms for crossing-number variants while extending them to surfaces and to rotation-system constraints. The explicit listing of the closure assumptions on D and the parameter-free character of the reduction (no hidden dependence on the particular drawing class beyond the stated hypotheses) are strengths that make the framework reusable.

minor comments (2)
  1. [Abstract] Abstract, paragraph beginning 'We fix a surface S': the parenthetical '(essentially)' before the parameter list could be replaced by an explicit statement of the precise parameter (genus plus crossing bound) to avoid any ambiguity about what is FPT.
  2. [Introduction] The manuscript would benefit from a short table in the introduction that lists the concrete D classes to which the framework is applied and the resulting runtime exponents, for quick reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance. The report accurately captures the framework's assumptions, reduction, and applications to crossing-number variants on surfaces.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper states an explicit reduction from the decision problem (existence of a drawing in D) to embeddability of a graph on a 2-dimensional simplicial complex whose size depends only on the genus and crossing bound parameters. The assumptions on class D (algorithmic membership test plus closure properties) are stated as inputs to the framework and are not derived from or equivalent to the claimed FPT result. No equations, fitted parameters, or self-citations are used to establish the central reduction; the result is therefore independent of its own outputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper rests on standard topological graph theory and parameterized complexity background; the only non-standard inputs are the algorithmic membership oracle and closure properties for each concrete D, which are treated as given per variant.

axioms (2)
  • domain assumption Membership in D is decidable by an algorithm whose runtime is absorbed into the FPT bound.
    Invoked in the statement of the framework (abstract).
  • domain assumption D is closed under restriction, crossing-free extension, and self-homeomorphisms of S.
    Required for the reduction to preserve membership (abstract).

pith-pipeline@v0.9.0 · 5847 in / 1326 out tokens · 23227 ms · 2026-05-23T20:23:54.427707+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 44 canonical work pages · 1 internal anchor

  1. [1]

    Agarwal, Boris Aronov, J \' a nos Pach, Richard Pollack, and Micha Sharir

    Pankaj K. Agarwal, Boris Aronov, J \' a nos Pach, Richard Pollack, and Micha Sharir. Quasi-planar graphs have a linear number of edges. Comb. , 17(1):1--9, 1997. https://doi.org/10.1007/BF01196127 doi:10.1007/BF01196127

    work page doi:10.1007/bf01196127 1997

  2. [2]

    Basic topology

    Mark Anthony Armstrong. Basic topology . Undergraduate Texts in Mathematics. Springer-Verlag, 1983

    work page 1983

  3. [3]

    T \' o th

    Sang Won Bae, Jean - Fran c ois Baffier, Jinhee Chun, Peter Eades, Kord Eickmeyer, Luca Grilli, Seok - Hee Hong, Matias Korman, Fabrizio Montecchiani, Ignaz Rutter, and Csaba D. T \' o th. Gap-planar graphs. Theor. Comput. Sci. , 745:36--52, 2018. https://doi.org/10.1016/j.tcs.2018.05.029 doi:10.1016/j.tcs.2018.05.029

    work page doi:10.1016/j.tcs.2018.05.029 2018

  4. [4]

    Martin Balko, Petr Hlin e n \' y , Tom \' a s Masa r \' k, Joachim Orthaber, Birgit Vogtenhuber, and Mirko H. Wagner. On the uncrossed number of graphs. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, September 18-20, 2024, Vienna, Austria , volume 320 of LIPIcs , pages 18:1--...

    work page doi:10.4230/lipics.gd.2024.18 2024

  5. [5]

    Graphs drawn with some vertices per face: Density and relationships

    Carla Binucci, Giuseppe Di Battista, Walter Didimo, Vida Dujmovic, Seok - Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini. Graphs drawn with some vertices per face: Density and relationships. IEEE Access , 12:68828--68846, 2024. https://doi.org/10.1109/ACCESS.2024.3401078 doi:10.1109/ACCESS.2024.3401078

    work page doi:10.1109/access.2024.3401078 2024

  6. [7]

    Hardness of approximation for crossing number

    Sergio Cabello. Hardness of approximation for crossing number. Discrete Comput. Geom. , 49(2):348--358, 2013. https://doi.org/10.1007/s00454-012-9440-6 doi:10.1007/s00454-012-9440-6

    work page doi:10.1007/s00454-012-9440-6 2013

  7. [8]

    Adding one edge to planar graphs makes crossing number and 1-planarity hard

    Sergio Cabello and Bojan Mohar. Adding one edge to planar graphs makes crossing number and 1-planarity hard. SIAM J. Comput. , 42(5):1803--1829, 2013. https://doi.org/10.1137/120872310 doi:10.1137/120872310

    work page doi:10.1137/120872310 2013

  8. [10]

    A subpolynomial approximation algorithm for graph crossing number in low-degree graphs

    Julia Chuzhoy and Zihan Tan. A subpolynomial approximation algorithm for graph crossing number in low-degree graphs. In STOC , pages 303--316. ACM , 2022. https://doi.org/10.1145/3519935.3519984 doi:10.1145/3519935.3519984

    work page doi:10.1145/3519935.3519984 2022

  9. [11]

    Testing graph isotopy on surfaces

    \'E ric Colin de Verdi \`e re and Arnaud de Mesmay. Testing graph isotopy on surfaces. Discrete & Computational Geometry , 51(1):171--206, 2014. https://doi.org/10.1007/s00454-013-9555-4 doi:10.1007/s00454-013-9555-4

    work page doi:10.1007/s00454-013-9555-4 2014

  10. [12]

    An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes

    \'E ric Colin de Verdi \`e re and Thomas Magnard. An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes. In Proceedings of the 29th European Symposium on Algorithms (ESA) , pages 32:1--32:17, 2021. Full improved version in arXiv:2107.06236v2. https://doi.org/10.4230/LIPIcs.ESA.2021.32 doi:10.4230/LIPIcs.ESA.2021.32

    work page doi:10.4230/lipics.esa.2021.32 2021

  11. [13]

    Embedding graphs into two-dimensional simplicial complexes

    \'E ric Colin de Verdi \`e re, Thomas Magnard, and Bojan Mohar. Embedding graphs into two-dimensional simplicial complexes. Computing in Geometry and Topology , 1(1):Article 6, 2022

    work page 2022

  12. [14]

    The monadic second-order logic of graphs

    Bruno Courcelle. The monadic second-order logic of graphs. I . recognizable sets of finite graphs. Inf. Comput. , 85(1):12--75, 1990. https://doi.org/10.1016/0890-5401(90)90043-H doi:10.1016/0890-5401(90)90043-H

    work page doi:10.1016/0890-5401(90)90043-h 1990

  13. [15]

    A survey on graph drawing beyond planarity

    Walter Didimo, Giuseppe Liotta, and Fabrizio Montecchiani. A survey on graph drawing beyond planarity. ACM Comput. Surv. , 52(1):4:1--4:37, 2019. https://doi.org/10.1145/3301281 doi:10.1145/3301281

    work page doi:10.1145/3301281 2019

  14. [16]

    Dynamic generators of topologically embedded graphs

    David Eppstein. Dynamic generators of topologically embedded graphs. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 599--608, 2003. URL: http://dl.acm.org/citation.cfm?id=644108.644208

    work page arXiv 2003

  15. [17]

    Lu \' e rbio Faria, Celina M. H. de Figueiredo, and Candido Ferreira Xavier de Mendon c a Neto. Splitting Number is NP -complete. Discret. Appl. Math. , 108(1-2):65--83, 2001

    work page 2001

  16. [18]

    Garey and David S

    Michael R. Garey and David S. Johnson. Crossing number is NP-complete . SIAM J. Algebr. Discrete Methods , 4(3):312--316, September 1983

    work page 1983

  17. [19]

    13 Petr Hliněný and Csenge Lili Ködmön

    Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica , 49(1):1--11, 2007. https://doi.org/10.1007/S00453-007-0010-X doi:10.1007/S00453-007-0010-X

    work page doi:10.1007/s00453-007-0010-x 2007

  18. [20]

    Computing crossing numbers in quadratic time

    Martin Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. , 68(2):285--302, 2004. https://doi.org/10.1016/j.jcss.2003.07.008 doi:10.1016/j.jcss.2003.07.008

    work page doi:10.1016/j.jcss.2003.07.008 2004

  19. [21]

    Parameterised partially-predrawn crossing number

    Thekla Hamm and Petr Hlin e n \' y . Parameterised partially-predrawn crossing number. In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany , volume 224 of LIPIcs , pages 46:1--46:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2022. https://doi.org/10....

    work page doi:10.4230/lipics.socg.2022.46 2022

  20. [22]

    Computing crossing numbers with topological and geometric restrictions

    Thekla Hamm, Fabian Klute, and Irene Parada. Computing crossing numbers with topological and geometric restrictions. CoRR , abs/2412.13092, 2024. https://doi.org/10.48550/ARXIV.2412.13092 doi:10.48550/ARXIV.2412.13092

    work page doi:10.48550/arxiv.2412.13092 2024

  21. [23]

    The splitting number of the complete graph

    Nora Hartsfield, Brad Jackson, and Gerhard Ringel. The splitting number of the complete graph. Graphs and Combinatorics , 1:311--329, 1985. https://doi.org/10.1007/BF02582960 doi:10.1007/BF02582960

    work page doi:10.1007/bf02582960 1985

  22. [24]

    Crossing number is hard for cubic graphs

    Petr Hlin e n \' y . Crossing number is hard for cubic graphs. Journal of Comb. Theory, Ser. B , 96(4):455--471, 2006. https://doi.org/10.1016/j.jctb.2005.09.009 doi:10.1016/j.jctb.2005.09.009

    work page doi:10.1016/j.jctb.2005.09.009 2006

  23. [25]

    Complexity of anchored crossing number and crossing number of almost planar graphs

    Petr Hlin e n \' y . Complexity of anchored crossing number and crossing number of almost planar graphs. In MFCS , volume 345 of LIPIcs , pages 59:1--59:17. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025. https://doi.org/10.4230/LIPIcs.MFCS.2025.59 doi:10.4230/LIPIcs.MFCS.2025.59

    work page doi:10.4230/lipics.mfcs.2025.59 2025

  24. [26]

    Crossing number is NP -hard for constant path-width (and tree-width)

    Petr Hlin e n \' y and Liana Khazaliya. Crossing number is NP -hard for constant path-width (and tree-width). In Juli \' a n Mestre and Anthony Wirth, editors, 35th International Symposium on Algorithms and Computation, ISAAC 2024, December 8-11, 2024, Sydney, Australia , volume 322 of LIPIcs , pages 40:1--40:15. Schloss Dagstuhl - Leibniz-Zentrum f \" u ...

    work page doi:10.4230/lipics.isaac.2024.40 2024

  25. [27]

    14 Heather Hulett, Todd G

    Petr Hlin e n \' y and Csenge Lili K \" o dm \" o n. Note on min- k -planar drawings of graphs. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, September 18-20, 2024, Vienna, Austria , volume 320 of LIPIcs , pages 8:1--8:10. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informat...

    work page doi:10.4230/lipics.gd.2024.8 2024

  26. [28]

    On hardness of the joint crossing number

    Petr Hlin e n \' y and Gelasio Salazar. On hardness of the joint crossing number. In ISAAC , volume 9472 of Lecture Notes in Computer Science , pages 603--613. Springer, 2015. https://doi.org/10.1007/978-3-031-49272-3\_4 doi:10.1007/978-3-031-49272-3\_4

    work page doi:10.1007/978-3-031-49272-3 2015

  27. [29]

    Splittings of graphs on surfaces

    Brad Jackson and Gerhard Ringel. Splittings of graphs on surfaces. Proceedings of the 1st Colorado Symposium on Graph Theory , pages 203--219, 1982

    work page 1982

  28. [30]

    Bart M. P. Jansen, Daniel Lokshtanov, and Saket Saurabh. A near-optimal planarization algorithm. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1802--1811, 2014. https://doi.org/10.1137/1.9781611973402.130 doi:10.1137/1.9781611973402.130

    work page doi:10.1137/1.9781611973402.130 2014

  29. [31]

    The density of fan-planar graphs

    Michael Kaufmann and Torsten Ueckerdt. The density of fan-planar graphs. Electron. J. Comb. , 29(1), 2022. https://doi.org/10.37236/10521 doi:10.37236/10521

    work page doi:10.37236/10521 2022

  30. [32]

    Ken - ichi Kawarabayashi and Bruce A. Reed. Computing crossing number in linear time. In STOC , pages 382--390. ACM , 2007. https://doi.org/10.1145/1250790.1250848 doi:10.1145/1250790.1250848

    work page doi:10.1145/1250790.1250848 2007

  31. [33]

    Graph-encoded maps

    S \'o stenes Lins. Graph-encoded maps. Journal of Combinatorial Theory, Series B , 32:171--181, 1982. URL: https://doi.org/10.1016/0095-8956(82)90033-8

    work page doi:10.1016/0095-8956(82)90033-8 1982

  32. [34]

    Liu and R.C

    P.C. Liu and R.C. Geldmacher. On the deletion of nonplanar edges of a graph. In Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ.,Boca Raton, Fla., 1979) , pages 727--738, 1979

    work page 1979

  33. [35]

    Crossing number in slightly superexponential time

    Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Jie Xue, and Meirav Zehavi. Crossing number in slightly superexponential time. In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 1412--1424, 2025. https://doi.org/10.1137/1.9781611978322.44 doi:10.1137/1.9781611978322.44

    work page doi:10.1137/1.9781611978322.44 2025

  34. [36]

    Graphs on surfaces

    Bojan Mohar and Carsten Thomassen. Graphs on surfaces . Johns Hopkins Studies in the Mathematical Sciences. Johns Hopkins University Press, 2001

    work page 2001

  35. [37]

    16 Nabil H Rafla.The good drawings Dn of the complete graph Kn

    Miriam M \" u nch and Ignaz Rutter. Parameterized algorithms for beyond-planar crossing numbers. In Stefan Felsner and Karsten Klein, editors, 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, September 18-20, 2024, Vienna, Austria , volume 320 of LIPIcs , pages 25:1--25:16. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Infor...

    work page internal anchor Pith review doi:10.4230/lipics.gd.2024.25 2024

  36. [38]

    Crossing numbers of graph embedding pairs on closed surfaces

    Seiya Negami. Crossing numbers of graph embedding pairs on closed surfaces. J. Graph Theory , 36(1):8--23, 2001. https://doi.org/10.1002/1097-0118(200101)36:1\ doi:10.1002/1097-0118(200101)36:1\

    work page doi:10.1002/1097-0118(200101)36:1 2001

  37. [39]

    o llenburg, Manuel Sorge, Soeren Terziadis, Ana \

    Martin N \" o llenburg, Manuel Sorge, Soeren Terziadis, Ana \" s Villedieu, Hsiang - Yun Wu, and Jules Wulms. Planarizing graphs and their drawings by vertex splitting. In GD , volume 13764 of Lecture Notes in Computer Science , pages 232--246. Springer, 2022. https://doi.org/10.1007/978-3-031-22203-0\_17 doi:10.1007/978-3-031-22203-0\_17

    work page doi:10.1007/978-3-031-22203-0 2022

  38. [40]

    Graphs drawn with few crossings per edge

    J \' a nos Pach and G \' e za T \' o th. Graphs drawn with few crossings per edge. Comb. , 17(3):427--439, 1997. https://doi.org/10.1007/BF01215922 doi:10.1007/BF01215922

    work page doi:10.1007/bf01215922 1997

  39. [41]

    Pelsmajer, Marcus Schaefer, and Daniel S tefankovi c

    Michael J. Pelsmajer, Marcus Schaefer, and Daniel S tefankovi c . Crossing numbers and parameterized complexity. In Graph Drawing, 15th International Symposium, GD 2007, Sydney, Australia, September 24-26, 2007. Revised Papers , volume 4875 of Lecture Notes in Computer Science , pages 31--36. Springer, 2007. https://doi.org/10.1007/978-3-540-77537-9\_6 do...

    work page doi:10.1007/978-3-540-77537-9 2007

  40. [42]

    Pelsmajer, Marcus Schaefer, and Daniel S tefankovi c

    Michael J. Pelsmajer, Marcus Schaefer, and Daniel S tefankovi c . Odd crossing number and crossing number are not the same. Discret. Comput. Geom. , 39(1-3):442--454, 2008. https://doi.org/10.1007/S00454-008-9058-X doi:10.1007/S00454-008-9058-X

    work page doi:10.1007/s00454-008-9058-x 2008

  41. [43]

    Pelsmajer, Marcus Schaefer, and Daniel S tefankovi c

    Michael J. Pelsmajer, Marcus Schaefer, and Daniel S tefankovi c . Crossing numbers of graphs with rotation systems. Algorithmica , 60(3):679--702, 2011. https://doi.org/10.1007/S00453-009-9343-Y doi:10.1007/S00453-009-9343-Y

    work page doi:10.1007/s00453-009-9343-y 2011

  42. [44]

    Crossing Numbers of Graphs

    Marcus Schaefer. Crossing Numbers of Graphs . Discrete mathematics and its applications. CRC Press, Taylor & Francis Group, 2017

    work page 2017

  43. [45]

    The graph crossing number and its variants: A survey

    Marcus Schaefer. The graph crossing number and its variants: A survey. Electron. J. Comb. , Dynamic Surveys, \#DS21, 2024. Eighth Edition: May 17, 2024. https://doi.org/10.37236/2713 doi:10.37236/2713

    work page doi:10.37236/2713 2024

  44. [46]

    Crossing numbers of beyond-planar graphs revisited

    Nathan van Beusekom, Irene Parada, and Bettina Speckmann. Crossing numbers of beyond-planar graphs revisited. J. Graph Algorithms Appl. , 26(1):149--170, 2022. https://doi.org/10.7155/jgaa.00586 doi:10.7155/jgaa.00586

    work page doi:10.7155/jgaa.00586 2022