The parameterized complexity of extending stack layouts

DOI10.4230/LIPICS.GD.2024.12MaRDI QIDQ6920471zbMATH OpenFDO

Authors Thomas Depian, Simon D. Fink, Robert Ganian, Martin Nöllenburg

Publication date 7 October 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.GD.2024.12

zbMATH Keywords

parameterized complexitybook embeddingstack layoutdrawing extension

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites work

• scientific article; zbMATH DE number 4051024 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 7559402 (Why is no real title available?)
• A Kuratowski-type theorem for planarity of partially embedded graphs
• A tight subexponential-time algorithm for two-page book embedding
• A trade-off between page number and page width of book embeddings of graphs
• Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
• Embedding planar graphs in four pages
• Extending Partial Orthogonal Drawings
• Extending orthogonal planar graph drawings is fixed-parameter tractable
• Extending partial 1-planar drawings
• Extending partial orthogonal drawings
• Extending upward planar graph drawings
• Four pages are indeed necessary for planar graphs
• Fundamentals of parameterized complexity
• Graph Drawing
• Graph-Theoretic Concepts in Computer Science
• Improved Circular Layouts
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• On parameterized algorithms for fixed-order book thickness with respect to the pathwidth of the vertex ordering
• On the upward book thickness problem: combinatorial and complexity results
• On the upward book thickness problem: combinatorial and complexity results
• Parameterized algorithms
• Parameterized algorithms for book embedding problems
• Parameterized algorithms for book embedding problems
• Partial and Constrained Level Planarity
• RNA structures with pseudo-knots: graph-theoretical, combinatorial, and statistical properties
• Testing Planarity of Partially Embedded Graphs
• The book thickness of a graph
• The complexity of colouring circle graphs (extended abstract)
• The pagewidth of trivalent planar graphs

This page was built for publication: The parameterized complexity of extending stack layouts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6920471)