Pith. sign in

REVIEW 3 major objections 4 minor 28 references

Structural Parameterizations of $k$-Planarity

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper proves that testing 1-planarity is NP-complete on near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and that local crossing number is hard to approximate within any constant factor even on…

desk verdict A solid and genuinely new map of k-planarity across structural parameters, but the abstract's headline strengthening rests on two asserted-and-unproved structural properties that need fixing. read the letter →

arxiv 2506.10717 v2 pith:RTLPC7J5 submitted 2025-06-12 cs.DS

Tatsuya Gima , Yasuaki Kobayashi , Yuto Okada This is my paper · ORCID
classification cs.DS MSC 05C1068Q2568R10
keywords 1-planargraphslocalcrossingnumberbeyondplanarityparameterizedcomplexitykernelizationtreedepthpathwidthfeedbackvertexset
topics P versus NP
open problems P versus NP
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

This paper is about where the intractability of k-planarity testing begins. It shows that deciding whether a graph can be drawn with at most one crossing per edge is NP-complete even for graphs obtainable from a planar graph by adding a single edge, with feedback vertex set number at most 3 and pathwidth at most 4. It also proves that the local crossing number has no polynomial-time constant-factor approximation unless P = NP, even for graphs that become forests after deleting two vertices. On the algorithmic side, it establishes fixed-parameter tractability for treedepth plus k, feedback edge set number, and path-free graph classes, and gives polynomial kernels for vertex cover and neighborhood diversity. The net effect is a near-complete map of which structural parameters make the problem tractable and which do not.

What carries the argument

The main workhorses are two reductions. A subdivision lemma states that $\mathrm{lcr}(G) \le k$ if and only if the graph obtained by subdividing every edge $k-1$ times is 1-planar, which converts general $k$ to the already-studied 1-planarity case with only a logarithmic treedepth blow-up and with feedback edge set number unchanged. A 'spoke' gadget, consisting of many internally disjoint length-2 paths from a new vertex to each vertex of a selected set, forces all spokes to be crossing-free in any $k$-planar drawing; this lets the paper import hardness from two-sided (2-layer) $k$-planarity and from Unary Bin Packing while keeping structural parameters tiny. The kernelization rests on counting twin classes and on a reduction rule for degree-2 vertices with identical neighborhoods, bounded by the $k$-planar edge bound and by the fact that $K_{7k+1,3}$ is not $k$-planar.

What would settle it

Construct an explicit path decomposition of width at most 4 for the graph in the proof of the paper's Theorem 9, and name one edge whose deletion leaves it planar. If neither can be produced, the near-planar pathwidth-4 NP-completeness statement is unsupported.

Watch

Extended reading notes

Core claim

The central claim is that the hardness boundary for k-planarity testing sits much lower than previously known. Testing 1-planarity is NP-complete even when the input graph is near-planar (planar plus one edge), has feedback vertex set number at most 3, and has pathwidth at most 4. Separately, the local crossing number cannot be approximated within any constant factor in polynomial time unless P = NP, even for graphs whose feedback vertex set number is at most 2. On the positive side, the paper proves fixed-parameter tractability for treedepth plus k, for feedback edge set number, and for $P_t$-free graphs parameterized by $t+k$, and gives polynomial kernels for vertex cover number and neighborhood diversity. It also proves W[1]-hardness for treedepth alone, twin cover number, and distance to path forest, so the positive treedepth result is tight in requiring $k$ as part of the parameter.

Load-bearing premise

The load-bearing premise is that the graph built in the Bin Packing reduction is genuinely near-planar and has pathwidth at most 4; the paper states both facts without giving a proof.

Editorial extensions

If this is right

  • 1-planarity testing remains NP-complete on constant-treewidth near-planar graphs, so any polynomial algorithm for that class must handle both the one-edge deviation from planarity and width at most 4 simultaneously.
  • Unless P = NP, there is no constant-factor approximation for the local crossing number even when deleting just two vertices makes the graph a forest.
  • k-planarity testing is FPT in treedepth plus k and in feedback edge set number, so these parameters give genuine tractability once k is charged to the parameter.
  • The problem admits polynomial-size kernels for vertex cover and neighborhood diversity, with explicit $O(\mathrm{vc}(G)^2 k^2 \sqrt{k})$ and $O(\mathrm{nd}(G)^2 k^3 \sqrt{k})$ bounds, computable in linear time.
  • k-planarity is W[1]-hard parameterized by treedepth alone, so the FPT treedepth-plus-k result cannot drop the $+k$ term unless W[1] = FPT.

Reading between the lines

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

  • Editorial inference: the unproved near-planarity and pathwidth claims in the paper's Corollary 11 are directly checkable from the construction; supplying an explicit path decomposition of width 4 and a single deletable edge would settle the strongest advertised result.
  • Editorial inference: the spoke gadget is a flexible forcing device, so the same many-parallel-length-2-paths construction could plausibly be reused to prove hardness for other drawing models or other width parameters such as bounded vertex integrity or shrub-depth.
  • Editorial inference: the subdivision lemma implies that future FPT or hardness results for 1-planarity automatically transfer to k-planarity with only a logarithmic penalty in treedepth, so progress on general k can largely be routed through the better-studied k = 1 case.
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 / 4 minor

Summary. The paper studies structural parameterizations of k-Planarity Testing and the local crossing number. It presents NP-hardness and inapproximability results for 1-planarity and local crossing number on graphs with feedback vertex set number 2 or 3, including near-planar graphs with pathwidth at most 4; W[1]-hardness results for treedepth, twin cover, and distance to path forest; and FPT algorithms and polynomial kernels parameterized by feedback edge set, treedepth+k, vertex cover, and neighborhood diversity. The positive results are accompanied by proofs in the appendix, and the negative results are obtained from reductions from Two-Sided k-Planarity and Unary Bin Packing.

Significance. If the results hold, the paper substantially sharpens known lower bounds: it improves the NP-completeness of 1-planarity on near-planar graphs to those with fvs ≤ 3 and pathwidth ≤ 4, and the (2−ε)-inapproximability of local crossing number to any constant factor on graphs with fvs ≤ 2. It also provides several tight FPT and kernelization results for the general k ≥ 1 case. The reductions are mostly explicit and the appendix contains detailed proofs of several technical lemmas. However, the central structural claims behind the headline lower bound are currently asserted rather than proved.

major comments (3)
  1. [3.2, before Corollary 11] Corollary 11 asserts that the graph G built in Theorem 9 is near-planar and has pathwidth at most 4, but neither property is proved anywhere in the text. The abstract's headline strengthening of the Cabello–Mohar result depends directly on these assertions; the authors should give an explicit edge e such that G−e is planar and an explicit path decomposition of width 4, and they should also state the (easy but currently implicit) argument that fvs(G) ≤ 3.
  2. [3.1, Theorem 6] In the proof of Theorem 6, the sentence 'the reduction used in Lemma 4 increases the treedepth by at most 3' is stated without justification. Since the W[1]-hardness with respect to treedepth is transferred through this reduction, a construction of an elimination forest of height td(G') ≤ td(G)+3 (or a precise reference) should be supplied.
  3. [3.2, Theorem 9 (reverse direction)] The reverse direction of the proof of Theorem 9 relies on the assertion that in the crossing-free spoke subdrawing there are two vertices v_i and v_j that lie on the outer cycle and all other v_ℓ are drawn inside the region bounded by that outer cycle. This is a topological claim about the planar subdrawing induced by the spokes and is not formally established; without it the extraction of the b regions and the counting argument do not follow. Please provide a proof or a precise citation.
minor comments (4)
  1. [3.3, Theorem 13 proof] In the proof of Theorem 13, 'add ℓ2 := B(bℓ1 + m) + 1 spokes between u2 and v2' should read 'between u2 and vi'; as written, the construction would not define b regions.
  2. [4.2, Lemma 19] In Lemma 19, the phrase 'degree at least 2 in V(G)\S' is confusing because V(G)\S is independent; it should say 'degree at least 2 in G' (or 'in S').
  3. [Abstract / Corollary 11] If the proof of Corollary 11 is added, please also state whether the pathwidth bound of 4 is tight or merely an upper bound, since the current wording suggests a tight structural bound.
  4. [3.1, Lemma 4] The proof of Lemma 4 is terse in its topological parts, especially in the construction of the closed curve C satisfying properties (4) and (5); adding a few more details about how the cyclic order of the edges incident to u is used would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the hardness results reduce from external NP-hard / W[1]-hard problems (Two-Sided k-Planarity, Bandwidth, Unary Bin Packing), and the FPT algorithms invoke independent results and external edge bounds; the unproved near-planarity/pathwidth claims in Corollary 11 are a completeness/correctness gap, not a circularity.

full rationale

The derivation chain is not circular. The central hardness reductions (Theorems 5, 6, 8, 9, 13) reduce from external problems: Theorem 5 and 8 use Two-Sided k-Planarity NP-completeness restricted to trees, citing the independent SoCG 2025 result [25] (with overlapping authors but containing externally verifiable constructions and an external theorem for NP-hardness); Theorem 6 uses W[1]-hardness of Bandwidth parameterized by treedepth on trees from [16] (an external paper with overlapping authors, used as an established theorem); Theorem 9 and Theorem 13 reduce from Unary Bin Packing, citing Garey–Johnson NP-completeness and Jansen et al. W[1]-hardness. The completeness arguments in Lemmas 4 and 9 do not fit any quantity to a target and do not define the target in terms of the algorithm's own output. The FPT results (Theorems 14, 16, 23; Corollary 25) use Lemma 1 (proved in the appendix), the 1-planarity FPT algorithms of Bannister–Cabello–Eppstein [2], the edge bound of Ackerman [1], the K_{7k+1,3} non-k-planarity criterion [6,32], and Proposition 17 from Nešetřil–Ossona de Mendez [29]; these are external, checkable facts rather than self-citation chains. Lemma 2's uncrossing argument is a genuine proof supplied in the appendix. The main weakness flagged by the skeptic—Corollary 11 asserts, without proof, that the Theorem 9 graph is near-planar and of pathwidth at most 4—is a missing-proof/correctness issue, not circularity: the claimed properties are not used to define the reduction's correctness, nor are they obtained by fitting parameters. Likewise, self-citations [16] and [25] are used for known hardness theorems, not to import a contested uniqueness ansatz, and the paper's own contributions (Lemma 4, Theorem 9, kernelization) remain independently meaningful even if those cited theorems were replaced. Hence the appropriate score is 1 (minor self-citation that is not load-bearing, with most results self-contained against external benchmarks), not a higher circularity score.

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

The paper introduces no new physical or mathematical entities and fits no numerical data. Its claims rest on standard complexity hypotheses and on published graph-drawing density and hardness theorems, several of which are authored by the same researchers. The main internal machinery is the spoke-gadget uncrossing lemma and the degree-2 reduction in the kernelization, which are proven in the text rather than postulated.

assumptions (7)
  • domain assumption Every k-planar graph with n vertices has at most 3.81 n sqrt(k) edges (Ackerman 2019).
    Invoked in Lemma 19 to bound the number of distinct vertex neighborhoods and in Lemma 24 to bound the vertex cover number; the paper uses this bound as an external proven fact.
  • domain assumption K_{7k+1,3} is not k-planar (Czap and Hudák 2012; Pfister 2025).
    Used in Corollary 20 to limit the number of false twins of a vertex outside a vertex cover, a key step in the kernel size bound.
  • domain assumption Two-Sided k-Planarity is NP-complete even on trees (Kobayashi, Okada, Wolff, SoCG 2025, Theorem 11).
    Starting point for Theorem 5 and for the hardness reduction in Lemma 4; the paper relies on this published result rather than proving it.
  • domain assumption Bandwidth is W[1]-hard parameterized by treedepth even on trees (Gima et al., TCS 2022).
    Used in Theorem 6 to transfer W[1]-hardness to k-Planarity Testing parameterized by treedepth; asserted without proof in this paper.
  • domain assumption Approximating bandwidth within any constant factor is NP-hard (Dubey, Feige, Unger 2011).
    Used in Lemma 7 to create the approximation gap for Two-Sided k-Planarity on trees and hence for Theorem 8.
  • domain assumption Unary Bin Packing is NP-complete and W[1]-hard parameterized by number of bins (Garey and Johnson 1983; Jansen et al. 2013).
    Source problem for the W[1]-hardness of distance to path forest (Theorem 9) and twin cover (Theorem 13), and for the small-item variant in Lemma 12.
  • standard math Standard complexity hypotheses P != NP, W[1] != FPT, and NP not subset coNP/poly.
    Needed to interpret the hardness, W[1]-hardness, and kernel lower bound statements; these are the standard assumptions of parameterized complexity theory, not introduced by this paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Structural Parameterizations of $k$-Planarity." pith.science (2026). https://pith.science/paper/RTLPC7J5

@misc{pith2026250610717,
  author       = {Pith},
  title        = {Pith review of: Structural Parameterizations of $k$-Planarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RTLPC7J5}},
  note         = {Machine review of arXiv:2506.10717}
}
abstract

The concept of $k$-planarity is extensively studied in the context of Beyond Planarity. A graph is $k$-planar if it admits a drawing in the plane in which each edge is crossed at most $k$ times. The local crossing number of a graph is the minimum integer $k$ such that it is $k$-planar. The problem of determining whether an input graph is $1$-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor $2 - \varepsilon$ for any $\varepsilon > 0$ [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of $k = 1$, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case $k \ge 1$ and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing $1$-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most $3$ and pathwidth at most $4$, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most $2$.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 11 canonical work pages

  1. [25]

    31 János Pach and Géza Tóth

    URL: https://doi.org/10.1007/s00373-015-1569-7, doi: 10.1007/S00373-015-1569-7. 31 János Pach and Géza Tóth. Graphs drawn with few crossings per edge.Comb., 17(3):427–439,

    work page doi:10.1007/s00373-015-1569-7

  2. [7]

    9 Andrew Drucker

    doi:10.1145/3301281. 9 Andrew Drucker. New limits to classical and quantum instance compression.SIAM J. Comput., 44(5):1443–1479,

    doi:10.1145/3301281

  3. [8]

    10 Chandan Dubey, Uriel Feige, and Walter Unger

    doi:10.1137/130927115. 10 Chandan Dubey, Uriel Feige, and Walter Unger. Hardness results for approximating the bandwidth. Journal of Computer and System Sciences , 77(1):62–90,

    work page doi:10.1137/130927115

  4. [11]

    13 Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak

    doi:10.1017/ 9781107415157. 13 Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Gregory Z. Gutin and Stefan Szeider, editors,Parameterized and Exact Computation - 8th International Symposium, IPEC 2013, Sophia Antipolis, France, September 4-6, 2013, Revised Selected Papers , volume 8246 ofLecture Notes...

    work page

  5. [12]

    14 Robert Ganian, Petr Hlinený, Jaroslav Nesetril, Jan Obdrzálek, and Patrice Ossona de Mendez

    doi:10.1007/978-3-319-03898-8_15. 14 Robert Ganian, Petr Hlinený, Jaroslav Nesetril, Jan Obdrzálek, and Patrice Ossona de Mendez. Shrub-depth: Capturing height of dense graphs. Log. Methods Comput. Sci. , 15(1),

    doi:10.1007/978-3-319-03898-8_15

  6. [13]

    doi:10.23638/LMCS-15(1:7)2019. 15 M. R. Garey and D. S. Johnson. Crossing number is NP-complete.SIAM Journal on Algebraic Discrete Methods, 4(3):312–316,

    doi:10.23638/lmcs-15(1:7)2019 2019

  7. [18]

    20 Michael Hoffmann, Chih-Hung Liu, Meghana M

    doi:10.1007/978-3-030-35802-0_24. 20 Michael Hoffmann, Chih-Hung Liu, Meghana M. Reddy, and Csaba D. Tóth. Simple topological drawings of k-planar graphs. In David Auber and Pavel Valtr, editors,Graph Drawing and Network Visualization - 28th International Symposium, GD 2020, Vancouver, BC, Canada, September 16-18, 2020, Revised Selected Papers , volume 12...

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

  8. [20]

    doi:10.1016/J.IPL.2018.04.012. T. Gima, Y. Kobayashi, and Y. Okada 17 25 Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff. Recognizing 2-Layer and Outerk- Planar Graphs. In Oswin Aichholzer and Haitao Wang, editors,Proc. 41st Annu. Sympos. Comput. Geom. (SoCG’25) , volume 332 of LIPIcs, pages 65:1–65:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    work page doi:10.1016/j.ipl.2018.04.012 2018

Show all 28 references
  1. [22]

    27 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Jie Xue, and Meirav Zehavi

    doi:10.1002/JGT.21630. 27 Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, Roohani Sharma, Jie Xue, and Meirav Zehavi. Crossing number in slightly superexponential time (extended abstract). InProceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025 ,...

    2025 doi

  2. [23]

    28 Miriam Münch, Maximilian Pfister, and Ignaz Rutter

    doi:10.1137/1.9781611978322.44. 28 Miriam Münch, Maximilian Pfister, and Ignaz Rutter. Exact and approximate k-planarity testing for maximal graphs of small pathwidth. InGraph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024 , volume 14760 ofLectur...

    doi

  3. [24]

    30 Jaroslav Nešetřil and Patrice Ossona de Mendez

    doi:10.1007/ 978-3-642-27875-4. 30 Jaroslav Nešetřil and Patrice Ossona de Mendez. On low tree-depth decompositions.Graphs Comb., 31(6):1941–1963,

    1941

  4. [28]

    18 Structural Parameterizations of k-Planarity u v r u v r Figure 9A crossing betweenPu and Pv can be removed by rerouting subcurves separating the crossing point

    doi:10.1016/J.COSREV.2022.100490. 18 Structural Parameterizations of k-Planarity u v r u v r Figure 9A crossing betweenPu and Pv can be removed by rerouting subcurves separating the crossing point. A Appendix: Missing Proofs ▶ Lemma 1 (⋆). LetG be a graph andk be a positive in...

    2022

  5. [1983]

    16 Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi

    doi:10.1137/0604033. 16 Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Ex- ploring the gap between treedepth and vertex cover through vertex integrity.Theor. Comput. Sci., 918:60–76,

    doi

  6. [1997]

    32 Maximilian Pfister

    doi:10.1007/BF01215922. 32 Maximilian Pfister. Algorithms and Combinatorics for Beyond Planar Graphs . Phd the- sis, Eberhard Karls Universität Tübingen, Tübingen, Germany,

    doi

  7. [2004]

    19 Petr Hliněný and Abhisekh Sankaran

    doi:10.1016/J.JCSS.2003.07.008. 19 Petr Hliněný and Abhisekh Sankaran. Exact crossing number parameterized by vertex cover. In Graph Drawing and Network Visualization - 27th International Symposium, GD 2019, volume 11904 ofLecture Notes in Computer Science , pages 307–319. Springer,

    2003 doi

  8. [2007]

    18 Martin Grohe

    doi:10.1007/S00453-007-0010-X. 18 Martin Grohe. Computing crossing numbers in quadratic time. J. Comput. Syst. Sci. , 68(2):285–302,

    doi

  9. [2009]

    4 Sergio Cabello and Bojan Mohar

    doi: 10.1016/J.JCSS.2009.04.001. 4 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,

    2009 doi

  10. [2011]

    doi:10.1016/j.jcss.2010.06.006

    Celebrating Karp’s Kyoto Prize. doi:10.1016/j.jcss.2010.06.006. 11 Vida Dujmovic, Seok-Hee Hong, Michael Kaufmann, János Pach, and Henry Förster. Beyond- planar graphs: Models, structures and geometric representations (dagstuhl seminar 24062). Dagstuhl Reports, 14(2):71–94,

    2010 doi

  11. [2012]

    16 Structural Parameterizations of k-Planarity 7 Éric Colin de Verdière and Thomas Magnard

    doi:10.1016/j.dam.2011.11.014. 16 Structural Parameterizations of k-Planarity 7 Éric Colin de Verdière and Thomas Magnard. An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes. In29th Annual European Symposium on Algorithms, ESA 2021 , vol...

    2011 doi

  12. [2013]

    5 Marek Cygan, Fedor V

    doi:10.1137/120872310. 5 Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh.Parameterized Algorithms. Springer,

    doi

  13. [2015]

    6 Július Czap and Dávid Hudák

    doi:10.1007/978-3-319-21275-3. 6 Július Czap and Dávid Hudák. 1-planarity of complete multipartite graphs.Discrete Applied Mathematics, 160(4):505–512,

    doi

  14. [2018]

    3 Hans L

    doi:10.7155/JGAA.00457. 3 Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, and Danny Hermelin. On problems without polynomial kernels. J. Comput. Syst. Sci. , 75(8):423–434,

    doi

  15. [2019]

    2 Michael J

    doi:10.1016/J.COMGEO.2019.101574. 2 Michael J. Bannister, Sergio Cabello, and David Eppstein. Parameterized complexity of 1-planarity. J. Graph Algorithms Appl. , 22(1):23–49,

    2019

  16. [2020]

    22 KlausJansen, StefanKratsch, DánielMarx, andIldikóSchlotter

    doi:10.1007/978-981-15-6533-5. 22 KlausJansen, StefanKratsch, DánielMarx, andIldikóSchlotter. Binpackingwithfixednumber of bins revisited.J. Comput. Syst. Sci. , 79(1):39–49, 2013.doi:10.1016/J.JCSS.2012.04.004. 23 Ken-ichi Kawarabayashi and Bruce A. Reed. Computing crossing n...

    2013

  17. [2021]

    34 Meirav Zehavi

    doi:10.1016/J.IPL.2020.106083. 34 Meirav Zehavi. Parameterized analysis and crossing minimization problems.Comput. Sci. Rev., 45:100490,

    2020

  18. [2022]

    17 Alexander Grigoriev and Hans L

    doi:10.1016/J.TCS.2022.03.021. 17 Alexander Grigoriev and Hans L. Bodlaender. Algorithms for graphs embeddable with few crossings per edge. Algorithmica, 49(1):1–11,

    2022 doi

  19. [2024]

    12 Fedor V

    doi:10.4230/DAGREP.14.2.71. 12 Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. Kernelization: Theory of Parameterized Preprocessing . Cambridge University Press,

    doi

  20. [2025]

    4230/LIPIcs.SoCG.2025.65

    URL:https://arxiv.org/abs/2412.04042, doi:10. 4230/LIPIcs.SoCG.2025.65. 26 Vladimir P. Korzhik and Bojan Mohar. Minimal obstructions for 1-immersions and hardness of 1-planarity testing.J. Graph Theory, 72(1):30–71,

    2025 arXiv

Pith tools

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