Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Recognizing 2-Layer and Outer $k$-Planar Graphs

T0 review · 3 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read This paper gives polynomial-time algorithms, for every fixed k, to recognize graphs that can be drawn with all vertices on two parallel lines or on a circle with at most k crossings per edge.

desk verdict Strong XP/FPT results for 2-layer and outer k-planar recognition, with the main proof gap being Lemma 13's reliance on an external same-author lemma that the authors do not fully transfer. read the letter →

arxiv 2412.04042 v3 pith:ST4SANER submitted 2024-12-05 cs.DS cs.CCcs.CG

Yasuaki Kobayashi , Yuto Okada , Alexander Wolff This is my paper · ORCID
classification cs.DScs.CCcs.CG MSC 05C1005C6205C8568Q2568R10
keywords 2-layerk-planargraphsouterrecognitionalgorithmslocalcrossingnumberparameterizedcomplexityXPXNLP-hardnessbandwidth
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 establishes that two natural recognition problems from graph drawing, one where vertices must lie on two parallel lines and one where they must lie on a circle, become polynomial-time solvable when the local crossing bound k is any fixed constant. In both settings an edge may cross at most k other edges. This settles a question left open in earlier work: outer 2-planar graphs can be recognized in polynomial time. The paper also shows that both problems are unlikely to have fixed-parameter-tractable algorithms, and that the variant with one prescribed layer order is fixed-parameter tractable.

What carries the argument

The load-bearing machinery is a separator-based splitting recurrence. For the two-layer problem, a set of 2k+1 consecutive vertices on one layer acts as a window; Lemma 8 shows that any connected component of the graph outside this window lies entirely to the left or entirely to the right, which lets the algorithm decompose the instance exactly as in the classical dynamic-programming technique for recognizing small-bandwidth graphs. For the outer problem, Lemma 13 guarantees that any consecutive pair (u,v) has a third vertex w such that both pairs {u,w} and {v,w} are pierced by at most k edges; the algorithm splits the instance into two smaller subinstances with pairs (u,w) and (w,v), recomputing crossing counts through a consistency condition that encodes the crossings inside the triangle formed by u, v, and w.

What would settle it

Find a biconnected outer k-planar graph in which some consecutive pair (u,v) has the property that for every third vertex w, at least one of the pairs {u,w} and {v,w} is pierced by more than k edges in every outer k-planar drawing; such a graph would make Lemma 13 false and break the split recurrence behind Theorem 12.

Watch

Extended reading notes

Core claim

For each fixed k, Two-Sided k-Planarity and Outer k-Planarity are in XP: the first is solved in time $2^{{O(k^3)}}$ $n^{{2k+O(1)}}$ and the second in time $2^{{O(k log k)}}$ $n^{{3k+O(1)}}$. The algorithms are dynamic programs that split a candidate drawing around small separators, a consecutive window of 2k+1 vertices on one layer for the two-layer case, and a third vertex that separates a circular drawing for the outer case. The paper further proves that Two-Sided k-Planarity is XNLP-complete even on trees, that Outer k-Planarity is XNLP-hard, and therefore that both are W[t]-hard for every t and unlikely to admit FPT algorithms under standard parameterized-complexity conjectures. For the one-sided version, where the order of one layer is part of the input, the paper gives an FPT algorithm running in $2^{{O(k log k)}}$ $n^{{O(1)}}$ time.

Load-bearing premise

The outer k-planar algorithm rests on Lemma 13, which says that in any outer k-planar drawing, a consecutive pair (u,v) always has a third vertex w such that both pairs {u,w} and {v,w} are pierced by at most k edges; the proof imports the corresponding statement from a triangulation lemma in a companion paper, so if that lemma does not cover non-maximal drawings, the splitting recurrence collapses.

Editorial extensions

If this is right

  • Outer 2-planar graphs can be recognized in polynomial time, answering the open problem posed by the authors of the linear-time outer 1-planar recognition algorithm.
  • For every fixed k, both 2-layer k-planar and outer k-planar recognition are in P, though the polynomial exponents grow with k.
  • The XNLP-hardness results imply that neither recognition problem is FPT with respect to k unless the parameterized complexity hierarchy collapses in a way the community regards as unlikely.
  • When the order of one layer is given, the one-sided 2-layer problem is FPT, so the fixed-order setting is genuinely easier than the two-sided one.
  • The local circular crossing number cannot be approximated within any constant factor in polynomial time, even for graphs that have feedback vertex number one.

Reading between the lines

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

  • Beyond the paper, the same separator-splitting scheme may extend to ℓ-layer k-planarity parameterized by ℓ+k, which the authors list as an open problem.
  • Beyond the paper, making explicit the tree decomposition implicitly constructed by the outer k-planar dynamic program could connect these XP results with the known quasi-polynomial recognition algorithm for outer k-planar graphs.
  • Beyond the paper, the bandwidth-based hardness reductions suggest that many local crossing-number variants with vertex-order constraints inherit hardness from linear-arrangement problems, so one might predict similar XNLP-hardness for related fixed-order book-embedding settings.
  • Beyond the paper, one could empirically test Lemma 13 for small k by exhaustively checking random outer k-planar drawings, which would provide computational evidence for the split recurrence before the companion triangulation lemma is fully formalized.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies the parameterized complexity of recognizing two families of graphs with bounded local crossing number: 2-layer k-planar graphs (bipartite graphs drawable on two parallel lines with at most k crossings per edge) and outer k-planar graphs (drawable on a circle with at most k crossings per edge). The main positive results are an XP-algorithm for Two-Sided k-Planarity running in 2^{O(k^3)} n^{2k+O(1)} time (Theorem 9) and an XP-algorithm for Outer k-Planarity running in 2^{O(k log k)} n^{3k+O(1)} time (Theorem 12), the latter resolving the open problem of polynomial-time recognition of outer 2-planar graphs. The paper also gives an FPT algorithm for One-Sided k-Planarity (Theorem 3), shows XNLP-completeness/hardness for the two-sided and outer variants (Theorems 11 and 19), proves weak NP-hardness for weighted one-sided variants, and derives an inapproximability result for the local circular crossing number on graphs with feedback vertex number 1 (Theorem 16). Most proofs are deferred to an appendix, and some key arguments are given only as sketches or by reference to an accompanying paper.

Significance. If the results are correct, this is a substantial contribution: it settles a natural open problem in beyond-planar graph recognition, gives the first recognition algorithms that are polynomial for every fixed k for both 2-layer k-planar and outer k-planar graphs, and places the corresponding problems in the parameterized hierarchy between XP and W[t]-hardness. The algorithmic ideas are clearly valuable: the one-sided FPT algorithm, the Saxe-style localization argument for the two-sided case, and the split recurrence for outer k-planar graphs are elegant and concrete. The paper also contains explicit running time bounds and several negative results that complement the positive ones. However, the outer k-planar XP algorithm rests on a lemma whose proof is delegated to a same-author paper and whose hypotheses are not verified in the present setting; this is load-bearing for Theorem 12.

major comments (3)
  1. [Appendix, Lemma 13] The proof of Lemma 13 is not self-contained and the transfer from [25, Lemma 6] is not demonstrated. The text says only that the authors of [25] 'did not use the maximality of G to show the existence of such an index j', and then applies the argument directly. But the graph G_{\vec e,R,\tau} is not maximal, has no outer cycle, and contains degree-one placeholder vertices t_1,...,t_\ell between u and v. The active-link argument in [25] operates on a maximal outer k-planar graph whose outer cycle edges exist and carry no crossings; none of these facts is established for G_{\vec e,R,\tau}. In particular, the recursive splitting of the pair {u,v} could produce an index j corresponding to one of the placeholder vertices t_i, which is not an element of R and therefore cannot be used as the vertex w required by Lemma 14. Since Lemma 14 is the engine of the XP algorithm for Outer k-Planarity, the proof of Theorem 12 is incomplete without a full proof of Lemma 13 or a precise reduction to [25, Lemma 6] that verifies all hypotheses, including why the selected vertex lies in R.
  2. [Section 5.1, first paragraph] The reduction to biconnected graphs is asserted without proof for general k: 'a graph is outer k-planar if and only if its biconnected components are outer k-planar; this can be shown in a similar manner as [32, Theorem 4] for k = 2.' This statement is used to justify restricting the input to biconnected graphs, and Theorem 12 depends on it. A proof or a reference that covers all k should be supplied, since the decomposition of an outer k-planar drawing at cut vertices is not entirely trivial when edges incident to the cut vertex may cross edges inside different blocks.
  3. [Appendix, Lemma 15] The enumeration bound in Lemma 15 is proved only as a sketch. The step 'Since R is a union of components in the graph obtained from G[V(G)\setminus{u,v}] by deleting the piercing edges' needs more justification: it must be shown that every R that appears as a feasible subproblem for a fixed pair {u,v} arises in this way from some valid drawing, and that distinct drawings cannot force a super-exponential number of candidate sets R beyond the counted 2^d component unions. This is less severe than the Lemma 13 issue, but it is used in the running time analysis of Theorem 12 and should be written out in full.
minor comments (5)
  1. [Section 3.1, Lemma 5] The recurrence uses the symbol \bigvee without a formal definition; please state explicitly that it denotes the logical OR over the listed choices for D_{i-1} and \chi_{i-1}.
  2. [Section 5.2, Theorem 16] The theorem says 'no polynomial-time c-approximation algorithm for Outer k-Planarity', but Outer k-Planarity is a decision problem. Please state that the inapproximability concerns the local circular crossing number, i.e., the minimum k for which the graph admits an outer k-planar drawing.
  3. [Appendix, Lemma 13] The phrase 'Property P1 ... assures that {u,v} has \ell \le k piercing edges' is not immediate from the definition of piercing and should be justified explicitly, especially because {u,v} need not be an edge.
  4. [Appendix, Lemma 14] There is a typo in the converse direction: 'Supposethatthereareconsistent' should be split into separate words. Additionally, the proof of the converse says 'It is not difficult to see' when combining D_H, D_1, and D_2; a sentence explaining why no new crossing exceeds k would improve readability.
  5. [Section 4.2, Theorem 11 proof] In the inequality for 2k, the case b=0 is not meaningful because k is defined via division by 2 and the reduction assumes b\ge 1 implicitly; please state this explicitly to avoid a minor edge-case ambiguity.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the XP-algorithms are built from proved recurrences and reductions, and the sole same-author lemma is an independently stated result, not the target recognition claim.

full rationale

I walked the derivation chain. The two-sided 2-layer k-planarity algorithm (Section 4.1) uses the paper's own Lemma 8 and a DP recurrence analogous to Lemma 5, with no parameter fitted from data and no prediction that reduces to an input. The one-sided FPT algorithm (Section 3.1) is similarly self-contained. For outer k-planarity, the only external dependency is Lemma 13, whose proof is delegated to Lemma 6 of [25], a paper sharing two authors with this one. That cited lemma concerns triangulations of maximal outer k-planar graphs and bounds on pierced vertex pairs; it is not the outer-k-planar recognition statement, and the current paper argues the transfer rather than assuming the desired theorem. The splitting recurrence in Lemma 14 and the enumeration bound in Lemma 15 are proved from the drawing properties, not from the table values. No equation in the paper equals its input by construction, and no central claim is forced by a self-citation chain. The same-author citation is load-bearing but it is a separate published mathematical result with its own proof, so under the stated rules it does not raise the circularity score. This is a non-finding: no significant circularity.

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

The central results rest on prior complexity-theoretic results (Bandwidth hardness), on structural graph-drawing results (the [25] triangulation lemma, the Pach-Toth edge bound), and on an unproved biconnected decomposition claim. No free parameters or invented entities are introduced; the clique-path gadget in Theorem 19 is a construction inside a reduction, not a postulated entity.

assumptions (6)
  • domain assumption A graph is outer k-planar if and only if its biconnected components are outer k-planar.
    Invoked at the start of Section 5.1 to restrict the XP algorithm to biconnected inputs; the paper cites the analogous k=2 result [32, Theorem 4] and states the general case 'can be shown in a similar manner' without proof.
  • domain assumption Lemma 6 of [25]: in an outer k-planar drawing, the pair (u,v) with at most k piercing edges admits a vertex w such that {u,w} and {v,w} are also pierced by at most k edges.
    This is the black box used to prove Lemma 13, the key structural step enabling the split recurrence for the Outer k-Planarity XP algorithm.
  • domain assumption Bandwidth is XNLP-hard on trees when parameterized by bandwidth.
    Standard result from [11,14]; used as the source problem in the XNLP-hardness reductions in Theorems 11 and 19.
  • domain assumption Bandwidth is NP-hard to approximate within any constant factor on trees.
    From [22]; used in Theorem 16 to prove inapproximability of Outer k-Planarity via a gap reduction.
  • domain assumption Outer k-planar graphs with n vertices have O(sqrt(k) n) edges (Pach-Toth bound).
    Used in the runtime analysis of Theorem 12 to substitute m = O(sqrt(k) n) and obtain the final n^{3k+O(1)} bound.
  • standard math XNLP contains W[t] for all t, and XNLP-hardness is evidence against FPT algorithms under the Pilipczuk-Wrochna conjecture.
    Standard parameterized complexity facts from [14,42]; used to interpret the hardness results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Recognizing 2-Layer and Outer $k$-Planar Graphs." pith.science (2026). https://pith.science/paper/ST4SANER

@misc{pith2026241204042,
  author       = {Pith},
  title        = {Pith review of: Recognizing 2-Layer and Outer $k$-Planar Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ST4SANER}},
  note         = {Machine review of arXiv:2412.04042}
}
abstract

The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two well-known variants of the problem are 2-layer crossing minimization and circular crossing minimization, where every vertex must lie on one of two layers, namely two parallel lines, or a circle, respectively. Both variants are NP-hard, but FPT with respect to the natural parameter. Recently, a local version of the crossing number has also received considerable attention. A graph is $k$-planar if it admits a drawing with at most $k$ crossings per edge. In contrast to the crossing number, recognizing $k$-planar graphs is NP-hard even if $k=1$. In this paper, we consider the two above variants in the local setting. The $k$-planar graphs that admit a straight-line drawing with vertices on two layers or on a circle are called 2-layer $k$-planar and outer $k$-planar graphs, respectively. We study the parameterized complexity of the two recognition problems with respect to $k$. For $k=0$, both problems can easily be solved in linear time. Two groups independently showed that outer 1-planar graphs can also be recognized in linear time [Hong et al., Algorithmica 2015; Auer et al., Algorithmica 2016]. One group asked whether outer 2-planar graphs can be recognized in polynomial time. Our main contribution consists of XP-algorithms for recognizing 2-layer $k$-planar graphs and outer $k$-planar graphs. We complement these results by showing that both recognition problems are XNLP-hard. This implies that both problems are W$[t]$-hard for every $t$ and that it is unlikely that they admit FPT-algorithms. On the other hand, we present an FPT-algorithm for recognizing 2-layer $k$-planar graphs where the order of the vertices on one layer is specified.

Figures

Figures reproduced from arXiv: 2412.04042 by the authors.

Figure 2
Figure 2. Setting k properly induces two balanced subsets of A. ◀ · · · a1 e0 en+1 P ≤ k an <X <Y [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Structural Parameterizations of $k$-Planarity

    cs.DS 2025-06 conditional novelty 7.0 of 10

    k-Planarity Testing stays NP-hard and hard to approximate on graphs with tiny feedback vertex sets, while becoming fixed-parameter tractable and kernelizable under vertex cover or treedepth parameters.

Reference graph

Works this paper leans on

49 extracted references · 15 canonical work pages · cited by 1 Pith paper

  1. [25]

    Bounding the Treewidth of Outer $k$-Planar Graphs via Triangulations

    Oksana Firman, Grzegorz Gutowski, Myroslav Kryven, Yuto Okada, and Alexander Wolff. Bounding the treewidth of outer k -planar graphs via triangulations. In Stefan Felsner and Karsten Klein, editors, 32nd Int. Symp. Graph Drawing & Network Vis. (GD) , volume 320 of LIPIcs , pages 14:1--14:17. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. UR...

    work page Pith review arXiv 2024

  2. [1]

    Eliminating crossings in ordered graphs

    Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. Eliminating crossings in ordered graphs. In Hans Bodlaender, editor, 19th Scand. Symp. Algorithm Theory (SWAT) , volume 294 of LIPIcs , pages 1:1--1:19. Schloss Dagstuhl -- Leibniz-Institut f \"u r Informatik, 2024. https://doi.org/10.4230/LI...

    doi:10.4230/lipics.swat.2024.1 2024

  3. [2]

    Edge partitions of complete geometric graphs

    Oswin Aichholzer, Johannes Obenaus, Joachim Orthaber, Rosna Paul, Patrick Schnider, Raphael Steiner, Tim Taubner, and Birgit Vogtenhuber. Edge partitions of complete geometric graphs. In Xavier Goaoc and Michael Kerber, editors, 38th Int. Symp. Comput. Geom. (SoCG) , volume 224 of LIPIcs , pages 6:1--6:16. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Infor...

    doi:10.4230/lipics.socg.2022.6 2022

  4. [3]

    $2$-Layer $k$-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth

    Patrizio Angelini, Giordano Da Lozzo, Henry Förster, and Thomas Schneck. 2-Layer k -planar graphs: Density, crossing lemma, relationships and pathwidth. The Computer Journal , 67(3):1005--1016, 2023. URL: https://arxiv.org/abs/2008.09329, https://doi.org/10.1093/comjnl/bxad038 doi:10.1093/comjnl/bxad038

    work page Pith review arXiv 2023

  5. [4]

    Brandenburg, Andreas Glei ner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber

    Christopher Auer, Christian Bachmaier, Franz J. Brandenburg, Andreas Glei ner, Kathrin Hanauer, Daniel Neuwirth, and Josef Reislhuber. Outer 1-planar graphs. Algorithmica , 74(4):1293--1320, 2016. https://doi.org/10.1007/S00453-015-0002-1 doi:10.1007/S00453-015-0002-1

    doi:10.1007/s00453-015-0002-1 2016

  6. [5]

    Parameterized complexity of 1-planarity

    Michael Bannister, Sergio Cabello, and David Eppstein. Parameterized complexity of 1-planarity. Journal of Graph Algorithms and Applications , 22(1):23--49, 2018. https://doi.org/10.7155/jgaa.00457 doi:10.7155/jgaa.00457

    doi:10.7155/jgaa.00457 2018

  7. [6]

    Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth

    Michael Bannister and David Eppstein. Crossing minimization for 1-page and 2-page drawings of graphs with bounded treewidth. Journal of Graph Algorithms and Applications , 22(4):577–606, 2018. https://doi.org/10.7155/jgaa.00479 doi:10.7155/jgaa.00479

    doi:10.7155/jgaa.00479 2018

  8. [7]

    Crossing reduction in circular layouts

    Michael Baur and Ulrik Brandes. Crossing reduction in circular layouts. In Juraj Hromkovic, Manfred Nagl, and Bernhard Westfechtel, editors, 30th Int. Workshop Graph-Theoretic Concepts Comput. Sci. (WG) , volume 3353 of LNCS , pages 332--343. Springer, 2004. https://doi.org/10.1007/978-3-540-30559-0_28 doi:10.1007/978-3-540-30559-0_28

    doi:10.1007/978-3-540-30559-0_28 2004

Show all 49 references
  1. [8]

    Parameterized algorithms for book embedding problems

    Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, and Martin N \" o llenburg. Parameterized algorithms for book embedding problems. Journal of Graph Algorithms and Applications , 24(4):603--620, 2020. https://doi.org/10.7155/jgaa.00526 doi:10.7155/jgaa.00526

    2020 doi

  2. [9]

    Min- k -planar drawings of graphs

    Carla Binucci, Aaron B \" u ngener, Giuseppe Di Battista, Walter Didimo, Vida Dujmovic, Seok - Hee Hong, Michael Kaufmann, Giuseppe Liotta, Pat Morin, and Alessandra Tappini. Min- k -planar drawings of graphs. Journal of Graph Algorithms and Applications , 28(2):1--35, 2024. h...

    2024 doi

  3. [10]

    Constrained and ordered level planarity parameterized by the number of levels

    Vacl \'a v Bla z ej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. Constrained and ordered level planarity parameterized by the number of levels. In Wolfgang Mulzer and Jeff M. Phillips, editors, 40th Annu. Sympos. Comput. Geom. (SoCG'24) ,...

    2024 arXiv

  4. [11]

    Bodlaender

    Hans L. Bodlaender. Parameterized complexity of bandwidth of caterpillars and weighted path emulation. In ukasz Kowalik, Micha Pilipczuk, and Pawe Rz a \. z ewski, editors, Graph-Theoretic Concepts Comput. Sci. (WG) , volume 12911 of LNCS , pages 15--27. Springer, 2021. https:...

    2021 doi

  5. [12]

    Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T

    Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima. XNLP -completeness for parameterized problems on graphs with a linear structure. In Holger Dell and Jesper Nederlof, editors, 17th Int. Symp. Paramet. & Exact Comput. (IPEC) , volume 249 of LIPIc...

    2022 doi

  6. [13]

    Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Micha Pilipczuk

    Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Micha Pilipczuk. On the complexity of problems on tree-structured graphs. In Holger Dell and Jesper Nederlof, editors, 17th Int. Symp. Paramet. & Exact Comput. (IPEC) , volume 249 of LIPIcs , pages 6:1--6:1...

    2022 doi

  7. [14]

    Bodlaender, Carla Groenland, Jesper Nederlof, and C \' e line M

    Hans L. Bodlaender, Carla Groenland, Jesper Nederlof, and C \' e line M. F. Swennenhuis. Parameterized problems complete for nondeterministic FPT time and logarithmic space. In 62nd IEEE Ann. Symp. Foundat. Comput. Sci. (FOCS) , pages 193--204, 2021. https://doi.org/10.1109/FO...

    2021

  8. [15]

    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 Journal on Computing , 42(5):1803--1829, 2013. https://doi.org/10.1137/120872310 doi:10.1137/120872310

    2013 doi

  9. [16]

    Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R

    Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, and David R. Wood. Product structure of graph classes with bounded treewidth. Combinatorics, Probability and Computin...

    2024 doi

  10. [17]

    Beyond outerplanarity

    Steven Chaplick, Myroslav Kryven, Giuseppe Liotta, Andre L \"o ffler, and Alexander Wolff. Beyond outerplanarity. In Fabrizio Frati and Kwan-Liu Ma, editors, 25th Int. Symp. Graph Drawing & Network Vis. (GD) , volume 10692 of LNCS , pages 546--559. Springer, 2018. URL: https:/...

    2018 arXiv

  11. [18]

    Fomin, ukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V. Fomin, ukasz Kowalik, Daniel Lokshtanov, D \' a niel Marx, Marcin Pilipczuk, Micha Pilipczuk, and Saket Saurabh. Parameterized Algorithms . Springer, 2015. https://doi.org/10.1007/978-3-319-21275-3 doi:10.1007/978-3-319-21275-3

    2015 doi

  12. [19]

    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

    2019 doi

  13. [20]

    A note on the complexity of one-sided crossing minimization of trees, 2023

    Alexander Dobler. A note on the complexity of one-sided crossing minimization of trees, 2023. arXiv. URL: https://arxiv.org/abs/2306.15339

    2023 arXiv

  14. [21]

    Downey and Michael R

    Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity . Texts in Computer Science. Springer, 2013. https://doi.org/10.1007/978-1-4471-5559-1 doi:10.1007/978-1-4471-5559-1

    2013 doi

  15. [22]

    Hardness results for approximating the bandwidth

    Chandan Dubey, Uriel Feige, and Walter Unger. Hardness results for approximating the bandwidth. Journal of Computer and System Sciences , 77(1):62--90, 2011. Celebrating Karp's Kyoto Prize. https://doi.org/10.1016/j.jcss.2010.06.006 doi:10.1016/j.jcss.2010.06.006

    2011 doi

  16. [23]

    Beyond-planar graphs: Models, structures and geometric representations ( Dagstuhl seminar 24062)

    Vida Dujmovi\' c , Seok-Hee Hong, Michael Kaufmann, J\' a nos Pach, and Henry F\" o rster. Beyond-planar graphs: Models, structures and geometric representations ( Dagstuhl seminar 24062). Dagstuhl Reports , 14(2):71--94, 2024. https://doi.org/10.4230/DagRep.14.2.71 doi:10.423...

    2024 doi

  17. [24]

    On the space and circuit complexity of parameterized problems: Classes and completeness

    Michael Elberfeld, Christoph Stockhusen, and Till Tantau. On the space and circuit complexity of parameterized problems: Classes and completeness. Algorithmica , 71(3):661--701, 2015. https://doi.org/10.1007/s00453-014-9944-y doi:10.1007/s00453-014-9944-y

    2015 doi

  18. [26]

    Parameterized Complexity Theory

    J \" o rg Flum and Martin Grohe. Parameterized Complexity Theory . Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006. https://doi.org/10.1007/3-540-29953-X doi:10.1007/3-540-29953-X

    2006 doi

  19. [27]

    Garey and David S

    Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman, 1979

    1979

  20. [28]

    Garey and David S

    Michael R. Garey and David S. Johnson. Crossing number is NP -complete. SIAM Journal on Algebraic Discrete Methods , 4(3):312--316, 1983. https://doi.org/10.1137/0604033 doi:10.1137/0604033

    1983 doi

  21. [29]

    Bodlaender

    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

    2007 doi

  22. [30]

    Computing crossing numbers in quadratic time

    Martin Grohe. Computing crossing numbers in quadratic time. Journal of Computer and System Sciences , 68(2):285--302, 2004. https://doi.org/10.1016/j.jcss.2003.07.008 doi:10.1016/j.jcss.2003.07.008

    2004 doi

  23. [31]

    A linear-time algorithm for testing outer-1-planarity

    Seok - Hee Hong, Peter Eades, Naoki Katoh, Giuseppe Liotta, Pascal Schweitzer, and Yusuke Suzuki. A linear-time algorithm for testing outer-1-planarity. Algorithmica , 72(4):1033--1054, 2015. https://doi.org/10.1007/S00453-014-9890-8 doi:10.1007/S00453-014-9890-8

    2015 doi

  24. [32]

    A linear-time algorithm for testing full outer-2-planarity

    Seok - Hee Hong and Hiroshi Nagamochi. A linear-time algorithm for testing full outer-2-planarity. Discrete Applied Mathematics , 255:234--257, 2019. https://doi.org/10.1016/j.dam.2018.08.018 doi:10.1016/j.dam.2018.08.018

    2019 doi

  25. [33]

    Paul C. Kainen. The book thickness of a graph. II . In 20th Southeastern Conf. Combin., Graph Theory, & Comput. (Boca Raton, FL, 1989) , volume 71, pages 127--132, 1990

    1989

  26. [34]

    Computing crossing number in linear time

    Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time. In 39th Ann. ACM Symp. Theory Comput. (STOC) , pages 382--390, 2007. https://doi.org/10.1145/1250790.1250848 doi:10.1145/1250790.1250848

    2007

  27. [35]

    An improved fixed-parameter algorithm for one-page crossing minimization

    Yasuaki Kobayashi, Hiromu Ohtsuka, and Hisao Tamaki. An improved fixed-parameter algorithm for one-page crossing minimization. In Daniel Lokshtanov and Naomi Nishimura, editors, 12th Int. Symp. Paramet. & Exact Comput. (IPEC) , volume 89 of LIPIcs , pages 25:1--25:12. Schloss ...

    2017 doi

  28. [36]

    A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization

    Yasuaki Kobayashi and Hisao Tamaki. A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. Algorithmica , 72:778--790, 2015. https://doi.org/10.1007/s00453-014-9872-x doi:10.1007/s00453-014-9872-x

    2015 doi

  29. [37]

    A faster fixed parameter algorithm for two-layer crossing minimization

    Yasuaki Kobayashi and Hisao Tamaki. A faster fixed parameter algorithm for two-layer crossing minimization. Information Processing Letters , 116(9):547--549, 2016. https://doi.org/10.1016/j.ipl.2016.04.012 doi:10.1016/j.ipl.2016.04.012

    2016 doi

  30. [38]

    Parameterized algorithms for fixed-order book drawing with bounded number of crossings per edge

    Yunlong Liu, Jie Chen, and Jingui Huang. Parameterized algorithms for fixed-order book drawing with bounded number of crossings per edge. In Weili Wu and Zhongnan Zhang, editors, Proc. 14th Int. Conf. Combin. Optim. Appl. (COCOA) , volume 12577 of LNCS , pages 562--576. Spring...

    2020 doi

  31. [39]

    On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering

    Yunlong Liu, Jie Chen, Jingui Huang, and Jianxin Wang. On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering. Theor. Comput. Sci. , 873:16--24, 2021. https://doi.org/10.1016/j.tcs.2021.04.021 doi:10.1016/j.tcs.2021.04.021

    2021 doi

  32. [40]

    One sided crossing minimization is NP -hard for sparse graphs

    Xavier Mu \ n oz, Walter Unger, and Imrich Vrt'o. One sided crossing minimization is NP -hard for sparse graphs. In Petra Mutzel, Michael J \" u nger, and Sebastian Leipert, editors, 9th Int. Symp. Graph Drawing (GD) , volume 2265 of LNCS , pages 115--123. Springer, 2001. http...

    2001 doi

  33. [41]

    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. Combinatorica , 17(3):427--439, 1997. https://doi.org/10.1007/BF01215922 doi:10.1007/BF01215922

    1997 doi

  34. [42]

    On space efficiency of algorithms working on structural decompositions of graphs

    Micha Pilipczuk and Marcin Wrochna. On space efficiency of algorithms working on structural decompositions of graphs. ACM Trans. Comput. Theory , 9(4), 2018. https://doi.org/10.1145/3154856 doi:10.1145/3154856

    2018 doi

  35. [43]

    Purchase, Christopher Pilcher, and Beryl Plimmer

    Helen C. Purchase, Christopher Pilcher, and Beryl Plimmer. Graph drawing aesthetics -- created by users, not algorithms. IEEE Transactions on Visualization and Computer Graphics , 18(1):81--92, 2012. https://doi.org/10.1109/TVCG.2010.269 doi:10.1109/TVCG.2010.269

    2012 doi

  36. [44]

    James B. Saxe. Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. SIAM J. Algebraic Discret. Methods , 1(4):363--369, 1980. https://doi.org/10.1137/0601042 doi:10.1137/0601042

    1980 doi

  37. [45]

    The graph crossing number and its variants: A survey

    Marcus Schaefer. The graph crossing number and its variants: A survey. Electronic Journal of Combinatorics , DS21, 2024. https://doi.org/10.37236/2713 doi:10.37236/2713

    2024 doi

  38. [46]

    Sz\' e kely, and Imrich Vrto

    Farhad Shahrokhi, Ondrej S\' y kora, L\' a szl\' o A. Sz\' e kely, and Imrich Vrto. On bipartite drawings and the linear arrangement problem. SIAM Journal on Computing , 30(6):1773--1789, 2001. https://doi.org/10.1137/S0097539797331671 doi:10.1137/S0097539797331671

    2001 doi

  39. [47]

    Methods for visual understanding of hierarchical system structures

    Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. , 11(2):109--125, 1981. https://doi.org/10.1109/TSMC.1981.4308636 doi:10.1109/TSMC.1981.4308636

    1981

  40. [48]

    Urschel and Jake Wellens

    John C. Urschel and Jake Wellens. Testing gap k -planarity is NP -complete. Information Processing Letters , 169:106083, 2021. https://doi.org/10.1016/j.ipl.2020.106083 doi:10.1016/j.ipl.2020.106083

    2021

  41. [49]

    Parameterized analysis and crossing minimization problems

    Meirav Zehavi. Parameterized analysis and crossing minimization problems. Computer Science Review , 45:100490, 2022. https://doi.org/10.1016/j.cosrev.2022.100490 doi:10.1016/j.cosrev.2022.100490

    2022

Pith tools

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