Pith. sign in

REVIEW 2 major objections 3 minor 169 references

Monotone Clustered Level Planarity

T0 review · 2 major / 3 minor · reviewed 2026-08-01 · deepseek-v4-flash

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

Pith's one-line read Clustered level planarity is FPT with vertex cover plus cluster count

desk verdict The paper is largely sound and genuinely interesting; the FPT proof has a load-bearing geometric gap that should be fixed, but this is a solid contribution worth reviewing. read the letter →

arxiv 2607.17930 v1 pith:VNETFC3Z submitted 2026-07-20 cs.DS cs.CG

Simon D. Fink , Matthias Pfretzschner , Ignaz Rutter , Marie Diana Sieper This is my paper · ORCID
classification cs.DScs.CG MSC 05C1005C8568Q17
keywords monotoneclusteredlevelplanarityclusteraugmentationparameterizedcomplexityfixed-parametertractabilityvertexcoverNP-completeness
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

Monotone Clustered Level Planarity (mCLP) asks whether a graph with fixed vertex levels can be drawn without crossings so that each cluster can be made connected by adding y-monotone edges. This paper determines which parameters make the problem tractable. On the negative side, mCLP remains NP-complete even for forests of constant-size trees with no isolated vertices and only a constant number of clusters or levels, which rules out fixed-parameter algorithms for almost every structural graph parameter. On the positive side, the problem is fixed-parameter tractable when the parameter is the vertex cover number plus the number of clusters. The key is showing that every yes-instance has a bounded-size subinstance admitting a tidy solution, then enumerating abstract blueprints of such subinstances, because standard kernelization fails for this non-hereditary problem.

What carries the argument

The central object is the tidy solution: a solution of a subinstance in which every omitted degree-2 vertex (an ear) is covered by a special augmentation edge with triangular incident faces, so that omitted vertices can be spliced back in without crossings. Solution normalizations show that any solution can be compressed to a tidy solution on a bounded-size subinstance, controlling transversals, ears, pendant vertices, and isolated vertices. Blueprints then let the algorithm enumerate all candidate bounded subinstances in FPT time: a blueprint is an abstract mCLP instance whose core matches the input and whose non-core vertices are dummies carrying only level-order information, and a polynom

What would settle it

Find a level graph that has a level-planar y-monotone embedding but for which no straight-line drawing exists that keeps all vertices on their assigned levels; such a counterexample would falsify the geometric assumption behind the pendant-vertex bound and would break the FPT proof.

Watch

Extended reading notes

Core claim

The central claim is that a yes-instance of mCLP admits a tidy solution on a subinstance whose size is bounded by a polynomial in the size of a vertex cover and the number of clusters, and that any such tidy solution can be extended to the entire instance by reinserting all omitted vertices. This yields a fixed-parameter algorithm: enumerate all bounded-size blueprints (abstract instances that match the input on a core subgraph), test each blueprint for realizability by dynamic programming, and answer yes exactly when some blueprint is realizable. The paper also proves that mCLP is NP-complete even for acyclic instances whose components have constant size, with either at most three clusters

Load-bearing premise

The FPT proof assumes a cited geometric straightening result: every level-planar drawing with y-monotone edges can be redrawn with straight-line edges while keeping every vertex on its prescribed level; this is used to bound the number of pendant vertices, and if it fails, the polynomial bound on subinstance size collapses.

Editorial extensions

If this is right

  • mCLP is para-NP-hard for treewidth, pathwidth, feedback vertex set, maximum degree, and essentially every graph-structural parameter except vertex cover, even when combined with a constant number of clusters or levels.
  • mCLP is fixed-parameter tractable when parameterized by vertex cover number plus the number of clusters, so instances with small vertex cover and few clusters can be solved exactly in FPT time.
  • Every yes-instance contains a bounded-size subinstance with a tidy solution, which directly yields an XP algorithm and provides a polynomial-time verifiable structural certificate.
  • The hardness reductions hold for acyclic, proper instances with fixed rotation, so these restrictions alone do not make the problem tractable.

Reading between the lines

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

  • The blueprint and solution-normalization framework is not specific to mCLP and could plausibly transfer to other non-hereditary constrained drawing problems where kernelization is blocked.
  • A natural next step is to decide whether the number of clusters can be dropped from the parameter; the paper's dynamic program would then have to track cluster-to-cluster mappings, which seems to be the main obstacle.
  • The polynomial bound on isolated vertices is the tightest part of the proof; a more direct combinatorial argument for isolated vertices could lower the parameter dependence or yield a kernel.
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

2 major / 3 minor

Summary. The paper studies the parameterized complexity of monotone Clustered Level Planarity (mCLP), a level-planar drawing problem with cluster connectivity constraints. It presents two main contributions. First, it strengthens the known NP-hardness of mCLP: the problem remains NP-complete even when the input is a forest in which every connected component has constant size, and either the number of levels or the number of clusters is a small constant (Theorems 4 and 5). Second, it gives an FPT algorithm for mCLP parameterized by the vertex cover number plus the number of clusters (Theorem 23). The FPT result is obtained by proving that every yes-instance has a bounded-size subinstance admitting a 'tidy' solution (Lemma 18), and then enumerating all 'blueprints' of bounded size and testing their realizability via dynamic programming (Lemma 21). The paper contains detailed proofs, several solution-normalization lemmas, and a discussion of why standard kernelization fails because mCLP is non-hereditary.

Significance. If correct, the paper essentially settles the parameterized complexity of mCLP for the most common graph-structural parameters, leaving only the vertex cover number without the cluster count as an open case. The proposed blueprint technique is an interesting way to handle non-hereditary planarity problems, and the explicit 'solution normalization' approach may be useful beyond this specific problem. The hardness results are strong and well motivated. The paper is well structured, provides many illustrative figures, and is transparent about the places where proofs are sketched. However, the FPT proof rests on a geometric redrawing assumption that is not supported by the cited reference, which makes the central algorithmic result currently not fully verified.

major comments (2)
  1. [§4.1, Lemma 13 (Solution Normalization 5)] The proof of Lemma 13 contains the claim: 'By the work of Pach and Tóth [18], we can assume that all edges of (E,A) are drawn as straight line segments without changing the y-coordinates of the vertices.' This is not a consequence of the cited paper, which concerns monotone straight-line drawings of planar graphs and does not prescribe vertex y-coordinates. The straightening step is essential: it lets the region K be treated as a simple polygon so that Proposition 2 can be applied to shortcut the augmentation path P. Without a correct justification, the bound on pendant vertices in Lemma 18 is unsupported, and with it the bounded-size subinstance Lemma 18 and the FPT enumeration in Theorem 23. The authors should either prove the fixed-y-coordinate straight-line redrawing claim (for example by citing a level-planar straight-line drawing theorem) or replace this step with a different argum
  2. [§4.1, Lemma 18 (proof)] The proof of Lemma 18 invokes '[3, Lemma 5]' to modify the drawing so that a shortcut edge can be inserted crossing-free and y-monotone. The cited lemma is about radial level planarity with fixed embedding and may not apply directly to the situation here, where augmentation edges and varying y-levels are involved. Since this step is used to bound the number of isolated vertices, it is also load-bearing for Lemma 18 and Theorem 23. The authors should either state the lemma from [3] and verify that its hypotheses hold, or give a self-contained proof of the shortcut property.
minor comments (3)
  1. [§3, Theorem 3] The proof of Theorem 3 is only sketched: 'We only sketch the correctness of the slightly modified construction here as it also follows analogously to the proof given by [11].' Since the new hardness theorems (Theorems 4 and 5) are built on this modified construction, the sketch should be expanded to state explicitly which modifications are made and why equivalence is preserved, or the theorem should be cited directly from [11] without proof.
  2. [§4.2, Lemma 21] In the dynamic-programming proof, the claim that Property (iii) of Claim 22 is independent of the choice of the mapping Phi_l' is only justified by a brief comment about counting ears in equivalence classes. This is plausible but should be formalized: the existence of an injective mapping between suitable vertices can be checked by a matching argument, and the cover assignment is itself a matching problem. The current proof does not give the precise complexity bound in terms of the input size, though the description suggests polynomial time.
  3. [General] Figure 2, which summarizes the parameter combinations for NP-hardness, is visually dense and the labels are small. A table with the exact parameters used in Theorems 3–5 might be easier to read. Minor typos and punctuation issues appear in the text, e.g., the missing space in 'we refer to the problem (y-)monotone Clustered Level Planarity (mCLP)' in the introduction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the FPT proof is self-contained; the hardness results build on a prior published theorem rather than assuming the target, and the cited straight-line/redrawing steps are external correctness risks, not circular reductions.

full rationale

The derivation chain for the central FPT result (Lemma 7 → Lemma 18 → blueprints → Theorem 23) does not reduce to its own inputs by construction. Lemma 7's tidy-subinstance characterization is proved by an explicit reinsertion argument, not by definition: the tidy conditions are chosen so that ears outside the subinstance can be reinserted, but the equivalence is nontrivial and two-sided. Lemma 18 bounds the size of a witness subinstance by applying solution normalizations whose proofs are self-contained except for two external geometric citations ([18] in Lemma 13 and [3, Lemma 5] in Lemma 18). Those are correctness/verification concerns, not circularity: they import external theorems, not the paper's target conclusion, and no parameter is fitted from data and then renamed as a prediction. The hardness section freely cites the authors' own [11, Theorem 3.2], but that is a published theorem with a proof sketch reproduced here; it is not assumed as the target result, and Theorems 4–5 are reductions from 3-Partition rather than re-statements of the input. The blueprint-based enumeration in Section 4 is self-referential in the sense that blueprints are built from a hypothetical solution, but the equivalence is mathematically substantive (yes-instance → bounded blueprint → tidy realization → yes-instance) and does not constitute circularity. The skeptical concern that Lemma 13's straight-line redrawing claim is not supported by Pach–Tóth [18] should be treated as a correctness risk, not a circularity finding.

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

The paper's central claim is a complexity classification, so there are no fitted constants. It depends on standard facts (level planarity algorithm, 3-Partition NP-completeness, degree bound in terms of vertex cover) and on the prior NP-completeness result [11] (same research group) whose full proof is not included. It also assumes a geometric straight-line redrawing property that is only loosely supported by the cited reference.

assumptions (6)
  • standard math Level Planarity is decidable in linear time (Jünger et al.)
    Used in the problem definition; cited as [16].
  • standard math 3-Partition is strongly NP-complete
    Basis of the reductions; cited as [15].
  • standard math Number of degree-≥3 vertices in a planar graph is O(vertex cover number)
    Used to bound the core size; cited as [12, Lemma 13.3].
  • domain assumption Theorem 3 from [11]: mCLP is NP-complete for proper acyclic instances with two clusters and five levels
    Base hardness theorem; the proof is only sketched in this paper, yet the new hardness results (Theorems 4 and 5) inherit from it.
  • domain assumption Any level-planar drawing can be straightened to straight-line segments while preserving y-coordinates of vertices
    Used in Lemma 13 to apply Proposition 2; cites [18] but that reference may not actually guarantee preservation of prescribed levels.
  • domain assumption Cornelsen and Wagner characterization of clustered planarity via augmentation edges
    Defines mCLP; cited as [4].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Monotone Clustered Level Planarity." pith.science (2026). https://pith.science/paper/VNETFC3Z

@misc{pith2026260717930,
  author       = {Pith},
  title        = {Pith review of: Monotone Clustered Level Planarity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VNETFC3Z}},
  note         = {Machine review of arXiv:2607.17930}
}
read the original abstract

We consider the combination of the two constrained planarity problems Level- and Clustered Planarity. Traditionally, level-planar drawings with convex clusters have been studied in this setting. Fink et al. (EuroCG 2024) recently introduced a different way of combining level- and clustered planarity by mimicking a classic characterization of clustered planarity in the level-planar setting: The problem (y-)monotone Clustered Level Planarity (mCLP) seeks a level-planar drawing in which it is possible to augment each cluster with edges that do not cross cluster boundaries so that it becomes connected while maintaining level-planarity. This is in line with previous research on clustered planarity that poses certain requirements on the augmentation edges that make each cluster connected, e.g., that they form a path. Fink et al. (EuroCG 2024) showed that mCLP is NP-complete even for biconnected single-source graphs and instances with a constant number of levels and clusters. We further classify the parameterized complexity of the mCLP problem by, on the one hand, showing hardness even for instances that consist of a forest with trees of bounded size, no isolated vertices, and a small constant number of either clusters or levels. This excludes fixed-parameter tractability for almost all graph-structural parameters, except for vertex cover, even in conjunction with the number of clusters. We complement this by showing fixed-parameter tractability when parameterizing by the vertex cover number and the number of clusters. A major obstacle is the fact that mCLP is non-hereditary, i.e., subinstances of yes-instances may be no-instances and vice versa, which makes it challenging to apply usual reduction techniques.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

169 extracted references · 70 canonical work pages

  1. [18]

    Extending Partial Orthogonal Drawings , doi =

    Patrizio Angelini and Ignaz Rutter and Sandhya. Extending Partial Orthogonal Drawings , doi =. 2021 , journal =

    2021

  2. [3]

    Fink and Ignaz Rutter , booktitle =

    Simon D. Fink and Ignaz Rutter , booktitle =. Constrained Planarity in Practice -- Engineering the Synchronized Planarity Algorithm , year =

  3. [1]

    Fink and Ignaz Rutter , booktitle =

    Simon D. Fink and Ignaz Rutter , booktitle =. Maintaining Triconnected Components Under Node Expansion , year =

  4. [2]

    Fink and Matthias Pfretzschner and Ignaz Rutter , booktitle =

    Simon D. Fink and Matthias Pfretzschner and Ignaz Rutter , booktitle =. Parameterized Complexity of Simultaneous Planarity , booktitleaddon =

  5. [4]

    Fink and Ignaz Rutter and Sandhya

    Simon D. Fink and Ignaz Rutter and Sandhya. to appear , title =. 2023 , keywords =

    2023

  6. [5]

    Fink and Matthias Pfretzschner and Ignaz Rutter , journal =

    Simon D. Fink and Matthias Pfretzschner and Ignaz Rutter , journal =. Experimental Comparison of. 2023 , doi =

    2023

  7. [6]

    Fink and Ignaz Rutter , journal =

    Thomas Bläsius and Simon D. Fink and Ignaz Rutter , journal =. Synchronized Planarity with Applications to Constrained Planarity Problems , year =. doi:10.1145/3607474 , publisher =

    work page doi:10.1145/3607474

  8. [7]

    2010 , title =

    Patrizio Angelini and Giuseppe. 2010 , title =. doi:10.1137/1.9781611973075.19 , editor =

    work page doi:10.1137/1.9781611973075.19 2010

Show all 169 references
  1. [8]

    International Journal of Foundations of Computer Science , title =

    Maurizio Patrignani , year =. International Journal of Foundations of Computer Science , title =. doi:10.1142/S0129054106004261 , number =

    doi

  2. [9]

    2011 , title =

    Pavel Klav. 2011 , title =. doi:10.1007/978-3-642-20877-5_28 , editor =

    2011 doi

  3. [10]

    Extending Partial Representations of Proper and Unit Interval Graphs , doi =

    Pavel Klav. Extending Partial Representations of Proper and Unit Interval Graphs , doi =. 2017 , journal =

    2017

  4. [11]

    2012 , title =

    Pavel Klav. 2012 , title =. doi:10.1007/978-3-642-33090-2_58 , editor =

    2012 doi

  5. [12]

    Extending partial representations of circle graphs , doi =

    Steven Chaplick and Radoslav Fulek and Pavel Klav. Extending partial representations of circle graphs , doi =. 2019 , journal =

    2019

  6. [13]

    2021 , title =

    Steven Chaplick and Philipp Kindermann and Jonathan Klawitter and Ignaz Rutter and Alexander Wolff , booktitle =. 2021 , title =. doi:10.1007/978-3-030-75242-2_24 , editor =

    2021 doi

  7. [14]

    2017 , title =

    Tomasz Krawczyk and Bartosz Walczak , booktitle =. 2017 , title =. doi:10.1007/978-3-319-68705-6_27 , editor =

    2017 doi

  8. [15]

    2014 , title =

    Steven Chaplick and Paul Dorbec and Jan Kratochv. 2014 , title =. doi:10.1007/978-3-319-12340-0_12 , editor =

    2014 doi

  9. [16]

    Handbook of Data Structures and Applications , year =

    Wen. Handbook of Data Structures and Applications , year =. doi:10.1201/9781420035179.ch32 , editor =

    doi

  10. [17]

    2018 , title =

    Anna Lubiw and Tillmann Miltzow and Debajyoti Mondal , booktitle =. 2018 , title =. doi:10.1007/978-3-030-04414-5_28 , editor =

    2018 doi

  11. [19]

    Extending Partial Representations of Interval Graphs , doi =

    Pavel Klav. Extending Partial Representations of Interval Graphs , doi =. 2016 , journal =

    2016

  12. [20]

    A Linear-Time Implementation of

    Matthias Pfretzschner , year =. A Linear-Time Implementation of

  13. [21]

    Journal of Computer and System Sciences , title =

    Norishige Chiba and Takao Nishizeki and Shigenobu Abe and Takao Ozawa , year =. Journal of Computer and System Sciences , title =. doi:10.1016/0022-0000(85)90004-2 , number =

    doi

  14. [22]

    Theoretical Computer Science , title =

    Shimon Even and Robert Endre Tarjan , year =. Theoretical Computer Science , title =. doi:10.1016/0304-3975(76)90086-4 , number =

    doi

  15. [23]

    1986 , title =

    Giuseppe. 1986 , title =. doi:10.1007/3-540-17218-1_65 , editor =

    1986 doi

  16. [24]

    Lempel and S

    A. Lempel and S. Even and I. Cederbaum , year =. Theory of Graphs , title =

  17. [25]

    Algorithm 447: efficient algorithms for graph manipulation , doi =

    John Edward Hopcroft and Robert Endre Tarjan , year =. Algorithm 447: efficient algorithms for graph manipulation , doi =. Communications of the

  18. [26]

    An Efficient Implementation of the

    Hsu, Wen-Lian , year =. An Efficient Implementation of the

  19. [27]

    Boyer , booktitle =

    John M. Boyer , booktitle =. 2005 , title =. doi:10.1007/978-3-540-31843-9_10 , pages =

    2005 doi

  20. [28]

    Charles Suer , year =. The

  21. [29]

    Boyer and Cristina G

    John M. Boyer and Cristina G. Fernandes and Alexandre Noma and Jos. Proceedings of the 3rd Workshop on Experimental and Efficient Algorithms (WEA'04) , year =. doi:10.1007/978-3-540-24838-5_10 , pages =

    doi

  22. [30]

    Leipert, Sebastian , year =

  23. [31]

    Grothaus and Adeel Mufti and T

    Gregory A. Grothaus and Adeel Mufti and T. M. Murali , year =. Algorithms for Molecular Biology , title =. doi:10.1186/1748-7188-1-15 , number =

    doi

  24. [32]

    Implementation of a planarity testing method using

    Cregten, Alex William and Hannesson, Hannes Kristj. Implementation of a planarity testing method using. 2017 , institution =

    2017

  25. [33]

    Handbook of Graph Drawing and Visualization , year =

    Markus Chimani and Carsten Gutwenger and Michael J. Handbook of Graph Drawing and Visualization , year =

  26. [34]

    Complexidade de constru

    Zanetti, Jo. Complexidade de constru. 2012 , institution =

    2012

  27. [35]

    Benzer , year =

    S. Benzer , year =. Proceedings of the National Academy of Sciences , title =. doi:10.1073/pnas.45.11.1607 , number =

    doi

  28. [36]

    2017 , title =

    Guido Br. 2017 , title =. doi:10.1137/1.9781611974782.130 , editor =

    2017 doi

  29. [37]

    , year =

    Tutte, W.T. , year =. Connectivity in Graphs , isbn =

  30. [38]

    Duke Mathematical Journal , title =

    Mac Lane, Saunders , year =. Duke Mathematical Journal , title =. doi:10.1215/S0012-7094-37-00336-3 , number =

    doi

  31. [39]

    Application of

    Gutwenger, Carsten , year =. Application of

  32. [40]

    Testing Mutual Duality of Planar Graphs , doi =

    Patrizio Angelini and Thomas Bl. Testing Mutual Duality of Planar Graphs , doi =. 2014 , journal =. 1303.1640 , eprinttype =

    2014 arXiv

  33. [41]

    1989 , title =

    G. 1989 , title =. doi:10.1109/sfcs.1989.63515 , pages =

    1989

  34. [42]

    J. A. La Poutr. 1992 , title =. doi:10.1007/3-540-55719-9_87 , pages =

    1992 doi

  35. [43]

    Italiano and Adam Karczmarz and Jakub Lacki and Eva Rotenberg , booktitle =

    Jacob Holm and Giuseppe F. Italiano and Adam Karczmarz and Jakub Lacki and Eva Rotenberg , booktitle =. 2018 , title =. doi:10.4230/LIPIcs.ESA.2018.46 , editor =

    2018 doi

  36. [44]

    La Poutr

    Johannes A. La Poutr. 1994 , title =. doi:10.1145/195058.195439 , publisher =

    1994

  37. [45]

    1990 , title =

    Giuseppe. 1990 , title =. doi:10.1007/bfb0032061 , pages =

    1990 doi

  38. [46]

    1992 , title =

    Jeffery Westbrook , booktitle =. 1992 , title =. doi:10.1007/3-540-55719-9_86 , pages =

    1992 doi

  39. [47]

    2017 , title =

    Fedarko, Marcus and Ghurye, Jay and Treagen, Todd and Pop, Mihai , booktitle =. 2017 , title =. doi:10.1007/978-3-319-73915-1 , editor =

    2017 doi

  40. [48]

    2019 , title =

    Guido Br. 2019 , title =. doi:10.1007/978-3-030-35802-0_39 , editor =

    2019 doi

  41. [49]

    New applications of

    Weiskircher, Rene , year =. New applications of. doi:10.22028/D291-25752 , language =

    doi

  42. [50]

    Optimal Orthogonal Graph Drawing with Convex Bend Costs , doi =

    Thomas Bl. Optimal Orthogonal Graph Drawing with Convex Bend Costs , doi =. 2016 , journal =

    2016

  43. [51]

    2020 , title =

    Walter Didimo and Giuseppe Liotta and Giacomo Ortali and Maurizio Patrignani , booktitle =. 2020 , title =. doi:10.1137/1.9781611975994.49 , pages =

    2020 doi

  44. [52]

    Finding a Minimum-depth Embedding of a Planar Graph in

    Patrizio Angelini and Giuseppe. Finding a Minimum-depth Embedding of a Planar Graph in. 2009 , journal =. doi:10.1007/s00453-009-9380-6 , number =

    2009 doi

  45. [53]

    Monma , year =

    Daniel Bienstock and Clyde L. Monma , year =. Algorithmica , title =. doi:10.1007/bf01840379 , number =

    doi

  46. [54]

    2003 , title =

    Petra Mutzel , booktitle =. 2003 , title =. doi:10.1007/3-540-45061-0_4 , editor =

    2003 doi

  47. [55]

    Proceedings of the

    Ye Zhang and Wai. Proceedings of the. 2013 , title =. doi:10.1109/ICCAD.2013.6691115 , editor =

    2013

  48. [56]

    The refined process structure tree , doi =

    Jussi Vanhatalo and Hagen V. The refined process structure tree , doi =. 2009 , journal =

    2009

  49. [57]

    Franken and J

    D. Franken and J. Ochs and K. Ochs , year =. Generation of wave digital structures for networks containing multiport elements , doi =

  50. [58]

    von Manteuffel and C

    A. von Manteuffel and C. Studerus , year =. Reduze 2 - Distributed Feynman Integral Reduction , eprint =

  51. [59]

    1999 , title =

    Zhi-Zhong Chen and Xin He and Chun-Hsi Huang , booktitle =. 1999 , title =. doi:10.1109/sffcs.1999.814603 , publisher =

    1999

  52. [60]

    Monma , year =

    Daniel Bienstock and Clyde L. Monma , year =. Networks , title =. doi:10.1002/net.3230190107 , number =

    doi

  53. [61]

    Biedl and Goos Kant and Michael Kaufmann , year =

    Therese C. Biedl and Goos Kant and Michael Kaufmann , year =. Algorithmica , title =. doi:10.1007/PL00009182 , number =

    doi

  54. [62]

    Italiano and Neil Sarnak , year =

    Zvi Galil and Giuseppe F. Italiano and Neil Sarnak , year =. Fully dynamic planarity testing with applications , doi =. Journal of the

  55. [63]

    Italiano and Thomas H

    David Eppstein and Zvi Galil and Giuseppe F. Italiano and Thomas H. Spencer , year =. Journal of Computer and System Sciences , title =. doi:10.1006/jcss.1996.0002 , number =

    1996

  56. [64]

    2014 , title =

    Patrizio Angelini and Giordano. 2014 , title =. 1404.6175 , eprinttype =

    2014 arXiv

  57. [65]

    Akitaya and Radoslav Fulek and Csaba D

    Hugo A. Akitaya and Radoslav Fulek and Csaba D. T. Recognizing Weak Embeddings of Graphs , doi =. 2019 , journal =

    2019

  58. [66]

    Journal of Graph Algorithms and Applications , title =

    Carsten Gutwenger and Karsten Klein and Petra Mutzel , year =. Journal of Graph Algorithms and Applications , title =. doi:10.7155/jgaa.00160 , number =

    doi

  59. [67]

    Embedding Simply Connected 2-Complexes in 3-Space --

    Johannes Carmesin , year =. Embedding Simply Connected 2-Complexes in 3-Space --. 1709.04659v3 , eprinttype =

    arXiv

  60. [68]

    Clustered planarity , doi =

    Pier Francesco Cortese and Giuseppe. Clustered planarity , doi =. Proceedings of the 21st Annual Symposium on Computational geometry (SCG'05) , year =

  61. [69]

    2002 , title =

    Giuseppe. 2002 , title =. doi:10.1007/3-540-45848-4_5 , pages =

    2002 doi

  62. [70]

    Cohen and Peter Eades , booktitle =

    Qing -Wen Feng and Robert F. Cohen and Peter Eades , booktitle =. 1995 , title =. doi:10.1007/bfb0030816 , pages =

    1995 doi

  63. [71]

    Graph Theory , doi =

    Reinhard Diestel , year =. Graph Theory , doi =

  64. [72]

    2018 , title =

    Radoslav Fulek and Jan Kyncl , booktitle =. 2018 , title =. doi:10.4230/LIPIcs.SoCG.2018.39 , pages =

    2018 doi

  65. [73]

    , year =

    Neuwirth, L. , year =. Mathematical Proceedings of the Cambridge Philosophical Society , title =. doi:10.1017/S0305004100043279 , number =

    doi

  66. [74]

    2018 , title =

    Arnaud de Mesmay and Yo'av Rieck and Eric Sedgwick and Martin Tancer , booktitle =. 2018 , title =. doi:10.1137/1.9781611975031.86 , pages =

    2018 doi

  67. [75]

    doi:10.1201/b15385 , editor =

    2014 , title =. doi:10.1201/b15385 , editor =

    2014 doi

  68. [76]

    Hadlock , year =

    F. Hadlock , year =. Finding a Maximum Cut of a Planar Graph in Polynomial Time , doi =

  69. [77]

    Journal of Combinatorial Theory, Series B , title =

    Frank Bernhart and Paul C Kainen , year =. Journal of Combinatorial Theory, Series B , title =. doi:10.1016/0095-8956(79)90021-2 , number =

    doi

  70. [78]

    Intersection Graphs in Simultaneous Embedding with Fixed Edges , doi =

    Michael J. Intersection Graphs in Simultaneous Embedding with Fixed Edges , doi =. 2009 , journal =

    2009

  71. [79]

    Computing

    Giordano. Computing. 2018 , journal =. doi:10.7155/jgaa.00461 , number =

    2018 doi

  72. [80]

    McGuffin , year =

    Nathalie Henry and Jean-Daniel Fekete and Michael J. McGuffin , year =. doi:10.1109/tvcg.2007.70582 , number =

    2007

  73. [81]

    Theoretical Computer Science , title =

    Giuseppe Liotta and Ignaz Rutter and Alessandra Tappini , year =. Theoretical Computer Science , title =. doi:10.1016/j.tcs.2021.05.012 , publisher =

    2021 doi

  74. [82]

    Embedding Simply Connected 2-Complexes in 3-Space --

    Johannes Carmesin , year =. Embedding Simply Connected 2-Complexes in 3-Space --. 1709.04642 , eprinttype =

    arXiv

  75. [83]

    Embedding Simply Connected 2-Complexes in 3-Space --

    Johannes Carmesin , year =. Embedding Simply Connected 2-Complexes in 3-Space --. 1709.04643 , eprinttype =

    arXiv

  76. [84]

    Bipartite Graphs, Upward Drawings, and Planarity , doi =

    Giuseppe. Bipartite Graphs, Upward Drawings, and Planarity , doi =. 1990 , journal =

    1990

  77. [85]

    and Spencer, Thomas H

    Eppstein, David and Galil, Zvi and Italiano, Giuseppe F. and Spencer, Thomas H. , year =. SIAM Journal on Computing , title =. doi:10.1137/S0097539794269072 , number =

    doi

  78. [86]

    2008 , title =

    Markus Chimani and Carsten Gutwenger and Mathias Jansen and Karsten Klein and Petra Mutzel , booktitle =. 2008 , title =. doi:10.1007/978-3-642-00219-9_12 , editor =

    2008 doi

  79. [87]

    2012 , title =

    Markus Chimani and Karsten Klein , booktitle =. 2012 , title =. doi:10.1007/978-3-642-36763-2_9 , editor =

    2012 doi

  80. [88]

    2012 , title =

    Patrizio Angelini and Marco Di Bartolomeo and Giuseppe. 2012 , title =. doi:10.1007/978-3-642-36763-2_8 , editor =

    2012 doi

  81. [89]

    GraphSET, a tool for simultaneous graph drawing , doi =

    Alejandro Estrella. GraphSET, a tool for simultaneous graph drawing , doi =. 2010 , journal =

    2010

  82. [90]

    Radial Level Planarity Testing and Embedding in Linear Time , doi =

    Christian Bachmaier and Franz. Radial Level Planarity Testing and Embedding in Linear Time , doi =. 2005 , journal =

    2005

  83. [91]

    1998 , title =

    Michael J. 1998 , title =. doi:10.1007/3-540-37623-2_17 , editor =

    1998 doi

  84. [92]

    Planar Graphs with Vertices in Prescribed Regions:models, algorithms, and complexity , url =

    Giordano. Planar Graphs with Vertices in Prescribed Regions:models, algorithms, and complexity , url =. 2015 , institution =

    2015

  85. [93]

    2007 , title =

    Martin Harrigan and Patrick Healy , booktitle =. 2007 , title =. doi:10.1007/978-3-540-77537-9_9 , editor =

    2007 doi

  86. [94]

    Level Planar Embedding in Linear Time , doi =

    Michael J. Level Planar Embedding in Linear Time , doi =. 2002 , journal =

    2002

  87. [95]

    Circle planarity of level graphs , url =

    Christian Bachmaier , year =. Circle planarity of level graphs , url =

  88. [96]

    Planarity Variants for Directed Graphs , url =

    Guido Br. Planarity Variants for Directed Graphs , url =. 2021 , institution =

    2021

  89. [97]

    Simpler algorithms for testing two-page book embedding of partitioned graphs , doi =

    Seok. Simpler algorithms for testing two-page book embedding of partitioned graphs , doi =. 2018 , journal =

    2018

  90. [98]

    Two-page book embedding and clustered graph planarity , number =

    Hong, Seok-Hee and Nagamochi, Hiroshi , year =. Two-page book embedding and clustered graph planarity , number =

  91. [99]

    Hammer and Alexander Kogan and Kazuhisa Makino and Bruno Simeone and Ondrej Cepek , year =

    Bert Randerath and Ewald Speckenmeyer and Endre Boros and Peter L. Hammer and Alexander Kogan and Kazuhisa Makino and Bruno Simeone and Ondrej Cepek , year =. Electronic Notes in Discrete Mathematics , title =. doi:10.1016/S1571-0653(04)00327-0 , pages =

    doi

  92. [100]

    Pelsmajer and Marcus Schaefer and Daniel

    Radoslav Fulek and Michael J. Pelsmajer and Marcus Schaefer and Daniel. Hanani. Thirty Essays on Geometric Graph Theory , year =. doi:10.1007/978-1-4614-0110-0_14 , pages =

    doi

  93. [101]

    2020 , title =

    Ignaz Rutter , booktitle =. 2020 , title =. doi:10.1007/978-981-15-6533-5_13 , editor =

    2020 doi

  94. [102]

    Simultaneous Graph Embeddings with Fixed Edges , doi =

    Elisabeth Gassner and Michael J. Simultaneous Graph Embeddings with Fixed Edges , doi =. Graph-Theoretic Concepts in Computer Science , year =

  95. [103]

    Advancements on

    Patrizio Angelini and Giordano. Advancements on. 2015 , journal =. doi:10.1016/j.tcs.2014.11.016 , pages =

    2015 doi

  96. [104]

    Boyer and Pier Francesco Cortese and Maurizio Patrignani and Giuseppe

    John M. Boyer and Pier Francesco Cortese and Maurizio Patrignani and Giuseppe. 2004 , title =. doi:10.1007/978-3-540-24595-7_3 , pages =

    2004 doi

  97. [105]

    Goldberg and Robert Endre Tarjan , year =

    Andrew V. Goldberg and Robert Endre Tarjan , year =. A new approach to the maximum-flow problem , doi =. Journal of the

  98. [106]

    International Journal of Foundations of Computer Science , title =

    Hubert De Fraysseix and Patrice Ossona De Mendez and Pierre Rosenstiehl , year =. International Journal of Foundations of Computer Science , title =. doi:10.1142/S0129054106004248 , eprint =

    doi

  99. [107]

    Journal of Computer and System Sciences , title =

    Giuseppe Liotta and Ignaz Rutter and Alessandra Tappini , year =. Journal of Computer and System Sciences , title =. doi:10.1016/j.jcss.2023.02.007 , pages =

    2023 doi

  100. [108]

    Geometric Graph Drawing Algorithms - Theory, Engineering and Experiments , doi =

    Radermacher, Marcel , year =. Geometric Graph Drawing Algorithms - Theory, Engineering and Experiments , doi =

  101. [109]

    Purchase and Jo-Anne Allder and David Carrington , year =

    Helen C. Purchase and Jo-Anne Allder and David Carrington , year =. Journal of Graph Algorithms and Applications , title =. doi:10.7155/jgaa.00054 , number =

    doi

  102. [110]

    Information Visualization , title =

    Colin Ware and Helen Purchase and Linda Colpoys and Matthew McGill , year =. Information Visualization , title =. doi:10.1057/palgrave.ivs.9500013 , number =

    doi

  103. [111]

    Testing Planarity of Partially Embedded Graphs , doi =

    Patrizio Angelini and Giuseppe. Testing Planarity of Partially Embedded Graphs , doi =. 2015 , journal =

    2015

  104. [112]

    Electronic Notes in Discrete Mathematics , title =

    Bernhard Haeupler and Robert Endre Tarjan , year =. Electronic Notes in Discrete Mathematics , title =. doi:10.1016/j.endm.2008.06.029 , pages =

    2008 doi

  105. [113]

    2003 , journal =

    Wen. 2003 , journal =. doi:10.1016/S0304-3975(02)00435-8 , number =

    2003 doi

  106. [114]

    2013 , title =

    Maurizio Patrignani , booktitle =. 2013 , title =

    2013

  107. [115]

    On-Line Planarity Testing , doi =

    Giuseppe. On-Line Planarity Testing , doi =. 1996-10 , journal =

    1996

  108. [116]

    Theoretical Computer Science , title =

    Shih, Wei-Kuan and Hsu, Wen-Lian , year =. Theoretical Computer Science , title =. doi:10.1016/s0304-3975(98)00120-0 , number =

    doi

  109. [117]

    2001 , title =

    Wen-Lian Hsu , booktitle =. 2001 , title =. doi:10.1007/3-540-44679-6_23 , editor =

    2001 doi

  110. [118]

    2009 , title =

    Alejandro Estrella. 2009 , title =. doi:10.1007/978-3-642-00219-9_17 , editor =

    2009 doi

  111. [119]

    Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices , doi =

    Thomas Bl. Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices , doi =. 2017 , journal =. 1506.05715 , eprinttype =

    2017 arXiv

  112. [120]

    2020 , title =

    Jacob Holm and Eva Rotenberg , booktitle =. 2020 , title =. doi:10.1145/3357713.3384249 , editor =. 1911.03449 , eprinttype =

    2020

  113. [121]

    2000 , title =

    Carsten Gutwenger and Petra Mutzel , booktitle =. 2000 , title =. doi:10.1007/3-540-44541-2_8 , editor =

    2000 doi

  114. [122]

    Dividing a Graph into Triconnected Components , doi =

    John Edward Hopcroft and Robert Endre Tarjan , year =. Dividing a Graph into Triconnected Components , doi =

  115. [123]

    2020 , title =

    Jacob Holm and Eva Rotenberg , booktitle =. 2020 , title =. doi:10.1137/1.9781611975994.146 , pages =

    2020 doi

  116. [124]

    2018 , title =

    Pier Francesco Cortese and Maurizio Patrignani , booktitle =. 2018 , title =. doi:10.1007/978-3-030-04414-5_2 , editor =

    2018 doi

  117. [125]

    2020 , title =

    Giuseppe Liotta and Ignaz Rutter and Alessandra Tappini , booktitle =. 2020 , title =. doi:10.1007/978-3-030-38919-2_51 , pages =

    2020 doi

  118. [126]

    Strip Planarity Testing for Embedded Planar Graphs , doi =

    Patrizio Angelini and Giordano. Strip Planarity Testing for Embedded Planar Graphs , doi =. 2016 , journal =

    2016

  119. [127]

    Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph , doi =

    Patrizio Angelini and Giuseppe. Testing the simultaneous embeddability of two graphs whose intersection is a biconnected or a connected graph , doi =. 2012 , journal =

    2012

  120. [128]

    Journal of Graph Algorithms and Applications , title =

    Marcus Schaefer , year =. Journal of Graph Algorithms and Applications , title =. doi:10.7155/jgaa.00298 , number =

    doi

  121. [129]

    2014 , title =

    Carsten Gutwenger and Petra Mutzel and Marcus Schaefer , booktitle =. 2014 , title =. doi:10.1137/1.9781611973198.9 , editor =

    2014 doi

  122. [130]

    Simultaneous Embedding of Planar Graphs , chapter =

    Thomas Bl. Simultaneous Embedding of Planar Graphs , chapter =. Handbook of Graph Drawing and Visualization , year =. 1204.5853 , isbn =

    arXiv

  123. [131]

    On simultaneous planar graph embeddings , doi =

    Peter Bra. On simultaneous planar graph embeddings , doi =. 2007 , journal =

    2007

  124. [132]

    Disconnectivity and relative positions in simultaneous embeddings , doi =

    Thomas Bl. Disconnectivity and relative positions in simultaneous embeddings , doi =. 2015 , journal =

    2015

  125. [133]

    , year =

    Booth, Kellogg S. , year =

  126. [134]

    Simultaneous

    Thomas Bl. Simultaneous. 2016 , journal =. doi:10.1145/2738054 , number =

    2016 doi

  127. [135]

    Radoslav Fulek and Csaba D. T. Atomic Embeddability, Clustered Planarity, and Thickenability , doi =. 2022 , journal =. 1907.13086v1 , eprintclass =

    2022 arXiv

  128. [136]

    2016 , journal =

    Patrizio Angelini and Giordano. 2016 , journal =. doi:10.1093/comjnl/bxw035 , number =

    2016 doi

  129. [137]

    Clustered Planarity with Pipes , doi =

    Patrizio Angelini and Giordano. Clustered Planarity with Pipes , doi =. 2019 , journal =

    2019

  130. [138]

    C-Planarity of C-Connected Clustered Graphs , doi =

    Pier Francesco Cortese and Giuseppe. C-Planarity of C-Connected Clustered Graphs , doi =. 2008 , journal =

    2008

  131. [139]

    Cohen and Peter Eades , booktitle =

    Qing-Wen Feng and Robert F. Cohen and Peter Eades , booktitle =. 1995 , title =. doi:10.1007/3-540-60313-1_145 , editor =

    1995 doi

  132. [140]

    Clustered Planarity Testing Revisited , doi =

    Radoslav Fulek and Jan Kyn. Clustered Planarity Testing Revisited , doi =. 2015 , journal =

    2015

  133. [141]

    2002 , title =

    Carsten Gutwenger and Michael J. 2002 , title =. doi:10.1007/3-540-36151-0_21 , editor =

    2002 doi

  134. [142]

    Journal of the ACM , title =

    Lengauer, Thomas , year =. Journal of the ACM , title =. doi:10.1145/65950.65952 , number =

  135. [143]

    A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem , doi =

    Thomas Bl. A New Perspective on Clustered Planarity as a Combinatorial Embedding Problem , doi =. 2016 , journal =. 1506.05673 , eprinttype =

    2016 arXiv

  136. [144]

    On-line maintenance of triconnected components with

    Giuseppe. On-line maintenance of triconnected components with. 1996 , journal =. doi:10.1007/bf01961541 , number =

    1996 doi

  137. [145]

    Booth and George S

    Kellogg S. Booth and George S. Lueker , year =. Journal of Computer and System Sciences , title =. doi:10.1016/S0022-0000(76)80045-1 , number =

    doi

  138. [146]

    The importance of being proper: (In clustered-level planarity and T-level planarity) , doi =

    Patrizio Angelini and Giordano. The importance of being proper: (In clustered-level planarity and T-level planarity) , doi =. 2015 , journal =

    2015

  139. [147]

    2004 , title =

    Michael Forster and Christian Bachmaier , booktitle =. 2004 , title =. doi:10.1007/978-3-540-24618-3_18 , editor =

    2004 doi

  140. [148]

    Theoretical Computer Science , title =

    Zvi Galil and Nimrod Megiddo , year =. Theoretical Computer Science , title =. doi:10.1016/0304-3975(77)90005-6 , number =

    doi

  141. [149]

    Opatrny , year =

    J. Opatrny , year =. Total Ordering Problem , doi =

  142. [150]

    Chan and Fabrizio Frati and Carsten Gutwenger and Anna Lubiw and Petra Mutzel and Marcus Schaefer , year =

    Timothy M. Chan and Fabrizio Frati and Carsten Gutwenger and Anna Lubiw and Petra Mutzel and Marcus Schaefer , year =. Journal of Graph Algorithms and Applications , title =. doi:10.7155/jgaa.00375 , number =

    doi

  143. [151]

    and Leiserson, Charles Eric and Rivest, Ronald L

    Cormen, Thomas H. and Leiserson, Charles Eric and Rivest, Ronald L. and Stein, Clifford , year =. Introduction to Algorithms , isbn =

  144. [152]

    Journal of Computational Geometry , title =

    Brückner, Guido and Rutter, Ignaz , year =. Journal of Computational Geometry , title =. doi:10.20382/JOCG.V14I1A3 , language =

    doi

  145. [153]

    Planarity Testing and Embedding based on the Haeupler-Tarjan Algorithm: Implemention and Experiments , type =

    Valentin Frey , year =. Planarity Testing and Embedding based on the Haeupler-Tarjan Algorithm: Implemention and Experiments , type =

  146. [154]

    Deriving Embeddings and Triconnectivity from the Haeupler-Tarjan Planarity Test , type =

    Tim-Florian Feulner , year =. Deriving Embeddings and Triconnectivity from the Haeupler-Tarjan Planarity Test , type =

  147. [155]

    The left-right planarity test , url =

    Brandes, Ulrik , year =. The left-right planarity test , url =

  148. [156]

    1999 , title =

    Boyer, John and Myrvold, Wendy , booktitle =. 1999 , title =

    1999

  149. [157]

    Schmidt , booktitle =

    Markus Chimani and Petra Mutzel and Jens M. Schmidt , booktitle =. 2007 , title =. doi:10.1007/978-3-540-77537-9_17 , pages =

    2007 doi

  150. [158]

    1975 , doi =

    Complexity Results for Multiprocessor Scheduling under Resource Constraints , journal =. 1975 , doi =

    1975

  151. [159]

    International Journal of Computational Geometry & Applications , volume =

    Mark de Berg and Amirali Khosravi , title =. International Journal of Computational Geometry & Applications , volume =. 2012 , url =. doi:10.1142/S0218195912500045 , timestamp =

    2012 doi

  152. [160]

    Completely connected clustered graphs , year = 2006, issn =

    Sabine Cornelsen and Dorothea Wagner , journal =. Completely connected clustered graphs , year = 2006, issn =. doi:10.1016/j.jda.2005.06.002 , keywords =

    2006 doi

  153. [161]

    Ordered Level Planarity and Its Relationship to Geodesic Planarity, Bi-Monotonicity, and Variations of Level Planarity , journal =

    Boris Klemz and G. Ordered Level Planarity and Its Relationship to Geodesic Planarity, Bi-Monotonicity, and Variations of Level Planarity , journal =. 2019 , doi =

    2019

  154. [162]

    35th International Symposium on Algorithms and Computation (ISAAC 2024) , pages =

    Da Lozzo, Giordano and Ganian, Robert and Gupta, Siddharth and Mohar, Bojan and Ordyniak, Sebastian and Zehavi, Meirav , title =. 35th International Symposium on Algorithms and Computation (ISAAC 2024) , pages =. 2024 , volume =. doi:10.4230/LIPIcs.ISAAC.2024.24 , annote =

    2024 doi

  155. [163]

    2024 , eprint=

    Clustered Planarity Variants for Level Graphs , author=. 2024 , eprint=

    2024

  156. [164]

    Journal of Graph Algorithms and Applications , author =

    Efficient C-Planarity Testing for Embedded Flat Clustered Graphs with Small Faces , volume =. Journal of Graph Algorithms and Applications , author =. 2009 , pages =. doi:10.7155/jgaa.00191 , language =

    2009 doi

  157. [165]

    Monotone drawings of planar graphs , journal =

    J. Monotone drawings of planar graphs , journal =. 2004 , doi =

    2004

  158. [166]

    2019 , publisher=

    Kernelization: theory of parameterized preprocessing , author=. 2019 , publisher=

    2019

  159. [167]

    M. R. Garey and David S. Johnson , title =. 1979 , isbn =

    1979

  160. [168]

    Radial Level Planarity with Fixed Embedding , journal =

    Guido Br. Radial Level Planarity with Fixed Embedding , journal =. 2021 , doi =

    2021

  161. [169]

    Fomin and Lukasz Kowalik and Daniel Lokshtanov and D

    Marek Cygan and Fedor V. Fomin and Lukasz Kowalik and Daniel Lokshtanov and D. Parameterized Algorithms , publisher =. 2015 , doi =

    2015

Pith tools

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