Pith. sign in

REVIEW 3 major objections 2 minor 45 references

Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms

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

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

Pith's one-line read This paper claims three new exact algorithms for stack and queue layouts—fixed-parameter in vertex integrity, n^(O(q*l)) in page width, and 2^(O(n)) for one-page queues—though the uploaded full text is a different manuscript.

desk verdict The abstract promises three algorithms, but the uploaded full text is a plant biology paper; as submitted, this is not a refereeable CS manuscript. read the letter →

arxiv 2508.16319 v1 pith:HRG5XY4F submitted 2025-08-22 cs.DS cs.CG

Thomas Depian , Simon D. Fink , Robert Ganian , Vaishali Surianarayanan This is my paper · ORCID
classification cs.DScs.CG MSC 68Q2505C8568R10
keywords stacklayoutsqueuevertexintegritypagewidthfixed-parameteralgorithmsRamseypruningexactgraphdrawing
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 aims to establish that three fundamental graph layout problems admit much faster exact algorithms than previously known. Specifically, it claims fixed-parameter tractability for minimum-page stack and queue layouts under the vertex integrity parameter, an n^(O(q*l)) algorithm for layouts of page width at most q, and a 2^(O(n)) algorithm for 1-page queue layouts. These results would settle an open question, remove a double-exponential dependency, and improve the previous n^(O(n)) bound. The uploaded full text, however, is a plant biology study about chickpea volatiles and soil resistance, so the promised proofs and analyses are not present in this document.

What carries the argument

The central objects are linear layouts (vertices on a line, edges assigned to pages) with two non-crossing conditions: stacks forbid crossings within a page, queues forbid nestings. The algorithmic machinery includes a vertex-integrity parameterization (deletion distance to a graph with small components) and a Ramsey-style pruning of irrelevant vertices, plus structural decompositions for page-width and queue-width that avoid double-exponential overhead.

What would settle it

Reading the full text as submitted: it contains no definitions of stack/queue layouts, no Ramsey pruning lemma, and no runtime proofs; the three algorithms announced in the abstract cannot be checked. To settle the claims, one would need the actual algorithmic manuscript with the proofs, or an independent derivation of the stated bounds.

Watch

Extended reading notes

Core claim

The paper's central claim is that three exact layout problems become tractable in new parameter regimes. (1) Minimum-page stack and queue layouts admit a fixed-parameter algorithm when parameterized by vertex integrity, using a 'Ramsey pruning technique' that generalizes prior vertex-cover parameterizations. (2) For any fixed page count l and page width bound q, layouts of width at most q can be found in n^(O(q*l)) time, the first such bound without a double-exponential dependency. (3) One-page queue layouts can be solved in 2^(O(n)) time, improving the previous n^(O(n)) algorithm.

Load-bearing premise

The load-bearing premise is that the document contains the technical body of the algorithms paper—the Ramsey pruning lemma, the runtime analysis, and the subexponential construction. The uploaded full text is a plant biology study, so this premise is false and the three algorithmic claims are unsupported by the present manuscript.

Editorial extensions

If this is right

  • Minimum-page stack and queue layouts become fixed-parameter tractable in vertex integrity, generalizing the known vertex-cover parameterization and addressing an open question.
  • Page-width-bounded layouts can be computed in n^(O(q*l)) time, so for constant page count and width the problem moves from double-exponential to polynomial time.
  • One-page queue layouts enter the subexponential regime with 2^(O(n)) time, placing them alongside the recent 2-page stack result.
  • Exact algorithms at these speeds could serve as practical baselines for layout optimization on moderate-sized graphs.

Reading between the lines

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

  • If the Ramsey pruning technique is sound, it may extend to other graph parameters that measure 'component-deletion' distance, such as neighborhood diversity or component-size measures, opening up FPT algorithms for other layout and coloring problems.
  • The n^(O(q*l)) page-width bound suggests the true bottleneck in page-width problems is not the page count but the width; a natural test would be whether real-world graph-drawing instances are width-bounded with small q.
  • The 2^(O(n)) algorithm for 1-page queues hints that the dominating cost is ordering vertices, not assigning pages; a possible next target is a O(c^n) algorithm with a small constant c, or a matching conditional lower bound.
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

3 major / 2 minor

Summary. The arXiv submission carries an abstract promising three algorithmic results for stack and queue layouts: (1) a fixed-parameter algorithm parameterized by vertex integrity via a 'Ramsey pruning technique', (2) an n^(O(q*l)) algorithm for l-page layouts of page width at most q, and (3) a 2^(O(n)) algorithm for 1-page queue layouts. The full text following the abstract is an unrelated plant biology manuscript on chickpea VOC emissions and soil electrical resistance. It contains no definitions of the layout problems, no graph-theoretic results, no algorithmic descriptions, and no runtime analyses. The document as submitted therefore cannot support any of the three claimed results.

Significance. If the three algorithmic claims were backed by correct proofs, they would represent substantial advances: the vertex-integrity FPT result would generalize the known vertex-cover parameterization, the n^(O(q*l)) bound would remove a double-exponential dependency, and the 2^(O(n)) algorithm would improve the previous n^(O(n)) baseline for 1-page queue layouts. The claims are concrete and falsifiable, which is a strength at the abstract level. However, the significance cannot be assessed because the technical body is missing entirely. The document as submitted provides no derivations, no lemmas, no experiments, and no reproducible artifacts.

major comments (3)
  1. [Full text (all sections after the abstract)] The full text is a plant biology study (chickpea VOCs and soil electrical resistance) with no content related to stacks, queues, page width, vertex integrity, or Ramsey theory. None of the three claimed algorithmic results is defined, proved, or even discussed beyond the abstract. This is a load-bearing absence: the central claims of the paper are entirely unsupported by the body. A manuscript whose technical content is a different paper cannot be accepted or meaningfully revised without a full rewrite.
  2. [Abstract, claim (1)] The 'Ramsey pruning technique' is introduced only by name. The abstract states that it yields an FPT algorithm parameterized by vertex integrity, but the document gives no statement of the pruning lemma, no proof that the parameter dependence is independent of n, and no runtime bound. Without these, the claimed generalization of the vertex-cover-parameterized algorithms cannot be verified.
  3. [Abstract, claims (2) and (3)] The claimed n^(O(q*l)) algorithm for page-width-bounded layouts and the claimed 2^(O(n)) algorithm for 1-page queue layouts are asserted with no algorithmic construction or complexity analysis. There is no comparison to the previous n^(O(n)) algorithm, no statement of the formal problem definitions, and no proof of correctness. These omissions remove the evidentiary basis for both results.
minor comments (2)
  1. [Metadata] The arXiv identifier cited for the full text (arXiv:2508.16328v1 [q-bio.OT]) differs from the reviewed abstract (arXiv:2508.16319), and the title of the full text does not match the title in the abstract. This suggests a submission inconsistency that should be resolved.
  2. [References] The reference list in the body is entirely from the plant-biology literature; there are no citations to stack/queue layout papers or to the ICALP'24 result mentioned in the abstract.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found; the submitted full text is an unrelated plant-biology manuscript, so the abstract's algorithmic claims have no derivations in the document and cannot be assessed for circularity.

full rationale

The abstract of arXiv:2508.16319 makes three algorithmic claims about stack and queue layouts, but the full text after the abstract is a plant-biology study of chickpea VOC emissions and soil electrical resistance. It contains no graph-theoretic definitions, no lemmas, no Ramsey pruning technique, no runtime analyses, and no equations that could form a derivation chain. Circularity requires that a claimed result reduces by construction to its own inputs—for example, a fitted parameter renamed as a prediction, or a load-bearing conclusion justified only by a self-citation. None of the abstract's statements exhibit such a reduction. The claims are instead positioned against external benchmarks (vertex cover parameterization, the ICALP'24 stack layout algorithm), which is the opposite of circular reasoning. The absence of the technical body is a serious document-integrity and verifiability problem, but it is not circularity. Under the hard rule that circularity must be demonstrated by quoting a specific reduction, no such step can be identified here, and the correct circularity score is 0.

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

The provided manuscript pairs a cs.DS abstract with an unrelated q-bio full text. At the abstract level, the only assumptions attributable to the claimed algorithms are the unstated Ramsey pruning bound, standard FPT conventions, and correctness of cited prior results. No free parameters or invented entities appear at the abstract level; the plant biology full text's measurement details belong to a different paper.

assumptions (3)
  • ad hoc to paper The newly developed 'Ramsey pruning technique' yields a bound depending only on the vertex integrity parameter, not on n, keeping the algorithm fixed-parameter tractable.
    Abstract item (1) attributes the FPT result to this technique. The bound and its proof are not stated in any supplied text, so its efficacy is an unverified premise of the claimed running time.
  • standard math Standard fixed-parameter tractability conventions (runtime of form f(k) * poly(n) in parameter k) and a standard computational model.
    The abstract's framing of 'fixed-parameter algorithm w.r.t. vertex integrity' presupposes these conventions without stating them.
  • domain assumption Correctness of the previously cited results: vertex-cover-parameterized layout algorithms and the ICALP'24 subexponential algorithm for 2-page stack layouts.
    Abstract items (1) and (3) define the new results as generalizations of, or counterparts to, these prior results; the present text supplies no independent derivation.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms." pith.science (2026). https://pith.science/paper/HRG5XY4F

@misc{pith2026250816319,
  author       = {Pith},
  title        = {Pith review of: Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HRG5XY4F}},
  note         = {Machine review of arXiv:2508.16319}
}
read the original abstract

In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layouts. A stack (resp. queue) layout places vertices along a line and assigns edges to pages so that no two edges on the same page are crossing (resp. nested). We provide three new algorithms which together substantially expand our understanding of these problems: (1) A fixed-parameter algorithm for computing minimum-page stack and queue layouts w.r.t. the vertex integrity of an n-vertex graph G. This result is motivated by an open question in the literature and generalizes the previous algorithms parameterizing by the vertex cover number of G. The proof relies on a newly developed Ramsey pruning technique. Vertex integrity intuitively measures the vertex deletion distance to a subgraph with only small connected components. (2) An n^(O(q * l)) algorithm for computing l-page stack and queue layouts of page width at most q. This is the first algorithm avoiding a double-exponential dependency on the parameters. The page width of a layout measures the maximum number of edges one needs to cross on any page to reach the outer face. (3) A 2^(O(n)) algorithm for computing 1-page queue layouts. This improves upon the previously fastest n^(O(n)) algorithm and can be seen as a counterpart to the recent subexponential algorithm for computing 2-page stack layouts [ICALP'24], but relies on an entirely different technique.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

45 extracted references · 20 canonical work pages

  1. [1]

    E liminating C rossings in O rdered G raphs

    Akanksha Agrawal, Sergio Cabello, Michael Kaufmann, Saket Saurabh, Roohani Sharma, Yushi Uno, and Alexander Wolff. E liminating C rossings in O rdered G raphs. In Hans L. Bodlaender, editor, Proc. 19th Scandinavian Workshop on Algorithm Theory (SWAT'24) , volume 294 of LIPIcs , pages 1:1--1:19. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuh...

    doi:10.4230/lipics.swat.2024.1 2024

  2. [2]

    Asymptotically tight bounds for some multicolored ramsey numbers

    Noga Alon and Vojtěch Rödl. Asymptotically tight bounds for some multicolored ramsey numbers

    work page

  3. [3]

    Bekos, Philipp Kindermann, and Tamara Mchedlidze

    Patrizio Angelini, Michael A. Bekos, Philipp Kindermann, and Tamara Mchedlidze. On mixed linear layouts of series-parallel graphs. Theoretical Computer Science , 936:129--138, 2022. https://doi.org/10.1016/J.TCS.2022.09.019 doi:10.1016/J.TCS.2022.09.019

    doi:10.1016/j.tcs.2022.09.019 2022

  4. [4]

    C rossing M inimization for 1-page and 2-page D rawings of G raphs with B ounded T reewidth

    Michael Bannister and David Eppstein. C rossing M inimization for 1-page and 2-page D rawings of G raphs with B ounded T reewidth. 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

  5. [5]

    Bekos, Martin Gronemann, and Chrysanthi N

    Michael A. Bekos, Martin Gronemann, and Chrysanthi N. Raftopoulou. An I mproved U pper B ound on the Q ueue N umber of P lanar G raphs. Algorithmica , 85(2):544--562, 2023. https://doi.org/10.1007/S00453-022-01037-4 doi:10.1007/S00453-022-01037-4

    doi:10.1007/s00453-022-01037-4 2023

  6. [6]

    On the U pward B ook T hickness P roblem: C ombinatorial and C omplexity R esults

    Sujoy Bhore, Giordano Da Lozzo, Fabrizio Montecchiani, and Martin N \"o llenburg. On the U pward B ook T hickness P roblem: C ombinatorial and C omplexity R esults. In Helen C. Purchase and Ignaz Rutter, editors, Proc. 29th International Symposium on Graph Drawing and Network Visualization (GD'21) , volume 12868 of Lecture Notes in Computer Science , page...

    doi:10.1007/978-3-030-92931-2 2021

  7. [7]

    Parameterized A lgorithms for B ook E mbedding P roblems

    Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, and Martin N \"o llenburg. Parameterized A lgorithms for B ook E mbedding P roblems. Journal of Graph Algorithms and Applications , 24(4):603--620, 2020. https://doi.org/10.7155/JGAA.00526 doi:10.7155/JGAA.00526

    doi:10.7155/jgaa.00526 2020

  8. [8]

    Parameterized A lgorithms for Q ueue L ayouts

    Sujoy Bhore, Robert Ganian, Fabrizio Montecchiani, and Martin N \"o llenburg. Parameterized A lgorithms for Q ueue L ayouts. Journal of Graph Algorithms and Applications , 26(3):335--352, 2022. https://doi.org/10.7155/JGAA.00597 doi:10.7155/JGAA.00597

    doi:10.7155/jgaa.00597 2022

Show all 45 references
  1. [9]

    Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C

    Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden. Subgraph I somorphism on G raph C lasses that E xclude a S ubstructure. Algorithmica , 82(12):3566--3587, 2020. https://doi.org/10.1007/S00453-020-00...

    2020 doi

  2. [10]

    Fan R. K. Chung, Frank Thomson Leighton, and Arnold L. Rosenberg. Embedding graphs in books: a layout problem with applications to VLSI design. SIAM Journal on Algebraic Discrete Methods , 8(1):33--58, 1987. https://doi.org/10.1137/0608002 doi:10.1137/0608002

    1987 doi

  3. [11]

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

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

    2015 doi

  4. [12]

    Fink, Robert Ganian, and Martin N \"o llenburg

    Thomas Depian, Simon D. Fink, Robert Ganian, and Martin N \"o llenburg. The P arameterized C omplexity O f E xtending S tack L ayouts. In Stefan Felsner and Karsten Klein, editors, Proc. 32nd International Symposium on Graph Drawing and Network Visualization (GD'24) , volume 3...

    2024 doi

  5. [13]

    Fink, Robert Ganian, and Martin N \" o llenburg

    Thomas Depian, Simon D. Fink, Robert Ganian, and Martin N \" o llenburg. The P eculiarities of E xtending Q ueue L ayouts. In Proc. 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'25) , 2025. To appear

    2025

  6. [14]

    G raph T heory, 4th E dition , volume 173 of Graduate T exts in M athematics

    Reinhard Diestel. G raph T heory, 4th E dition , volume 173 of Graduate T exts in M athematics . Springer, 2012

    2012

  7. [15]

    Dregi, and Pim van 't Hof

    P l Gr n s Drange, Markus S. Dregi, and Pim van 't Hof. On the computational complexity of vertex integrity and component order connectivity. Algorithmica , 76(4):1181--1202, 2016. URL: https://doi.org/10.1007/s00453-016-0127-x, https://doi.org/10.1007/S00453-016-0127-X doi:10...

    2016 doi

  8. [16]

    Vida Dujmovi \'c , Gwena \"e l Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood. Planar G raphs H ave B ounded Q ueue- N umber. Journal of the ACM , 67(4):22:1--22:38, 2020. https://doi.org/10.1145/3385731 doi:10.1145/3385731

    2020 doi

  9. [17]

    Vida Dujmovic, Pat Morin, and David R. Wood. Layout of G raphs with B ounded T ree- W idth. SIAM Journal on Computing , 34(3):553--579, 2005. https://doi.org/10.1137/S0097539702416141 doi:10.1137/S0097539702416141

    2005 doi

  10. [18]

    Vida Dujmovi \'c and David R. Wood. On L inear L ayouts of G raphs. Discrete Mathematics & Theoretical Computer Science , 6(2):339--358, 2004. https://doi.org/10.46298/DMTCS.317 doi:10.46298/DMTCS.317

    2004 doi

  11. [19]

    Vida Dujmovic and David R. Wood. Graph T reewidth and G eometric T hickness P arameters. Discrete & Computational Geometry , 37(4):641--670, 2007. https://doi.org/10.1007/S00454-007-1318-7 doi:10.1007/S00454-007-1318-7

    2007 doi

  12. [20]

    Vida Dujmovi \'c and David R. Wood. On the B ook T hickness of k- T rees. Discrete Mathematics & Theoretical Computer Science , 13(3):39--44, 2011. https://doi.org/10.46298/DMTCS.550 doi:10.46298/DMTCS.550

    2011 doi

  13. [21]

    Solving I nteger L inear P rograms with a S mall N umber of G lobal V ariables and C onstraints

    Pavel Dvor \' a k, Eduard Eiben, Robert Ganian, Dusan Knop, and Sebastian Ordyniak. Solving I nteger L inear P rograms with a S mall N umber of G lobal V ariables and C onstraints. In Carles Sierra, editor, Proc 26th International Joint Conference on Artificial Intelligence (I...

    2017 doi

  14. [22]

    he complexity landscape of decompositional parameters for ILP: P rograms with few global variables and constraints

    Pavel Dvo r \'a k, Eduard Eiben, Robert Ganian, Du s an Knop, and Sebastian Ordyniak. he complexity landscape of decompositional parameters for ILP: P rograms with few global variables and constraints. Artificial Intelligence , 300:103561, 2021. https://doi.org/10.1016/J.ARTIN...

    2021

  15. [23]

    On S tructural P arameterizations of the B ounded- D egree V ertex D eletion P roblem

    Robert Ganian, Fabian Klute, and Sebastian Ordyniak. On S tructural P arameterizations of the B ounded- D egree V ertex D eletion P roblem. Algorithmica , 83(1):297--336, 2021. https://doi.org/10.1007/S00453-020-00758-8 doi:10.1007/S00453-020-00758-8

    2021 doi

  16. [24]

    Parameterized C omplexity in G raph D rawing ( D agstuhl S eminar 21293)

    Robert Ganian, Fabrizio Montecchiani, Martin N \"o llenburg, and Meirav Zehavi. Parameterized C omplexity in G raph D rawing ( D agstuhl S eminar 21293). Dagstuhl Reports , 11(6):82--123, 2021. https://doi.org/10.4230/DAGREP.11.6.82 doi:10.4230/DAGREP.11.6.82

    2021 doi

  17. [25]

    A T ight S ubexponential- T ime A lgorithm for T wo- P age B ook E mbedding

    Robert Ganian, Haiko M \" u ller, Sebastian Ordyniak, Giacomo Paesani, and Mateusz Rychlicki. A T ight S ubexponential- T ime A lgorithm for T wo- P age B ook E mbedding. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, Proc. 51st International Coll...

    2024 doi

  18. [26]

    On S tructural P arameterizations of the E dge D isjoint P aths P roblem

    Robert Ganian, Sebastian Ordyniak, and Maadapuzhi Sridharan Ramanujan. On S tructural P arameterizations of the E dge D isjoint P aths P roblem. Algorithmica , 83(6):1605--1637, 2021. https://doi.org/10.1007/S00453-020-00795-3 doi:10.1007/S00453-020-00795-3

    2021 doi

  19. [27]

    Garey and David S

    Michael R. Garey and David S. Johnson. C omputers and I ntractability: A G uide to the T heory of NP - C ompleteness . W. H. Freeman, 1979

    1979

  20. [28]

    Exploring the gap between treedepth and vertex cover through vertex integrity

    Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, and Yota Otachi. Exploring the gap between treedepth and vertex cover through vertex integrity. Theoretical Computer Science , 918:60--76, 2022. https://doi.org/10.1016/J.TCS.2022.03.021 doi:10.1016/J.TCS.2022.03.021

    2022 doi

  21. [29]

    Parameterized V ertex I ntegrity R evisited

    Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized V ertex I ntegrity R evisited. In Rastislav Kr \' a lovic and Anton \' n Kucera, editors, Proc. 49th International Symposium on Mathematical Foundations of Computer Science (MFCS'24) , volum...

    2024 doi

  22. [30]

    Christian Haslinger and Peter F. Stadler. RNA S tructures with P seudo-knots: G raph-theoretical, C ombinatorial, and S tatistical P roperties. Bulletin of Mathematical Biology , 61(3):437--467, 1999. https://doi.org/10.1006/bulm.1998.0085 doi:10.1006/bulm.1998.0085

    1999

  23. [31]

    Lenwood S. Heath. Embedding outerplanar graphs in small books. SIAM Journal on Algebraic Discrete Methods , 8(2):198--218, 1987. https://doi.org/10.1137/0608018 doi:10.1137/0608018

    1987 doi

  24. [32]

    Heath and Sriram V

    Lenwood S. Heath and Sriram V. Pemmaraju. Recognizing L eveled- P lanar D ags in L inear T ime. In Franz - Josef Brandenburg, editor, Proc. 3rd International Symposium on Graph Drawing and Network Visualization (GD'95) , volume 1027 of Lecture Notes in Computer Science , pages...

    1996 doi

  25. [33]

    Heath and Arnold L

    Lenwood S. Heath and Arnold L. Rosenberg. Laying out G raphs U sing Q ueues. SIAM Journal on Computing , 21(5):927--958, 1992. https://doi.org/10.1137/0221055 doi:10.1137/0221055

    1992 doi

  26. [34]

    L evel P lanar E mbedding in L inear T ime

    Michael J \" u nger and Sebastian Leipert. L evel P lanar E mbedding in L inear T ime. In Jan Kratochv \' l, editor, Proc. 7th International Symposium on Graph Drawing and Network Visualization (GD'99) , volume 1731 of Lecture Notes in Computer Science , pages 72--81. Springer...

    1999 doi

  27. [35]

    L evel P lanar E mbedding in L inear T ime

    Michael J \" u nger and Sebastian Leipert. L evel P lanar E mbedding in L inear T ime. Journal of Graph Algorithms and Applications , 6(1):67--113, 2002. https://doi.org/10.7155/JGAA.00045 doi:10.7155/JGAA.00045

    2002 doi

  28. [36]

    Level P lanarity T esting in L inear T ime

    Michael J \"u nger, Sebastian Leipert, and Petra Mutzel. Level P lanarity T esting in L inear T ime. In Sue Whitesides, editor, Proc. 6th International Symposium on Graph Drawing and Network Visualization (GD'98) , volume 1547 of Lecture Notes in Computer Science , pages 224--...

    1998 doi

  29. [37]

    Transforming S tacks into Q ueues: M ixed and S eparated L ayouts of G raphs

    Julia Katheder, Michael Kaufmann, Sergey Pupyrev, and Torsten Ueckerdt. Transforming S tacks into Q ueues: M ixed and S eparated L ayouts of G raphs. In Olaf Beyersdorff, Michal Pilipczuk, Elaine Pimentel, and Kim Thang Nguyen, editors, Proc. 42nd Symposium on Theoretical Aspe...

    2025 doi

  30. [38]

    Fine-grained M eta- T heorems for V ertex I ntegrity

    Michael Lampis and Valia Mitsou. Fine-grained M eta- T heorems for V ertex I ntegrity. Logical Methods in Computer Science , 20, 2024. https://doi.org/10.46298/LMCS-20(4:18)2024 doi:10.46298/LMCS-20(4:18)2024

    2024 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. Theoretical Computer Science , 873:16--24, 2021. https://doi.org/10.1016/J.TCS.2021.04.021 doi:10.1016/J.TCS....

    2021 doi

  32. [40]

    Rosenberg

    Arnold L. Rosenberg. Book embeddings and wafer-scale integration. In Proc. 17th Southeastern International Conference on Combinatorics, Graph Theory, and Computing , volume 54, pages 217--224, 1986

    1986

  33. [41]

    James B. Saxe. Dynamic- P rogramming A lgorithms for R ecognizing S mall- B andwidth G raphs in P olynomial T ime. SIAM Journal on Algebraic Discrete Methods , 1(4):363--369, 1980. https://doi.org/10.1137/0601042 doi:10.1137/0601042

    1980 doi

  34. [42]

    A T rade-off between P age N umber and P age W idth of B ook E mbeddings of G raphs

    Elena St \"o hr. A T rade-off between P age N umber and P age W idth of B ook E mbeddings of G raphs. Information and Computation , 79(2):155--162, 1988. https://doi.org/10.1016/0890-5401(88)90036-3 doi:10.1016/0890-5401(88)90036-3

    1988 doi

  35. [43]

    The pagewidth of trivalent planar graphs

    Elena St \"o hr. The pagewidth of trivalent planar graphs. Discrete Mathematics , 89(1):43--49, 1991. https://doi.org/10.1016/0012-365X(91)90398-L doi:10.1016/0012-365X(91)90398-L

    1991 doi

  36. [44]

    On the queue-number of graphs with bounded tree-width

    Veit Wiechert. On the queue-number of graphs with bounded tree-width. Electron. J. Comb. , 24(1):1, 2017. https://doi.org/10.37236/6429 doi:10.37236/6429

    2017 doi

  37. [45]

    Embedding P lanar G raphs in F our P ages

    Mihalis Yannakakis. Embedding P lanar G raphs in F our P ages. Journal of Computer and System Sciences , 38(1):36--67, 1989. https://doi.org/10.1016/0022-0000(89)90032-9 doi:10.1016/0022-0000(89)90032-9

    1989 doi

Pith tools

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