<div class="csl-bib-body">
<div class="csl-entry">Depian, T., Fink, S. D., Ganian, R., & Nöllenburg, M. (2024). The Parameterized Complexity Of Extending Stack Layouts. In <i>32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)</i> (pp. 12:1-12:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.GD.2024.12</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/208043
-
dc.description.abstract
An ℓ-page stack layout (also known as an ℓ-page book embedding) of a graph is a linear order of the vertex set together with a partition of the edge set into ℓ stacks (or pages), such that the endpoints of no two edges on the same stack alternate. We study the problem of extending a given partial ℓ-page stack layout into a complete one, which can be seen as a natural generalization of the classical NP-hard problem of computing a stack layout of an input graph from scratch. Given the inherent intractability of the problem, we focus on identifying tractable fragments through the refined lens of parameterized complexity analysis. Our results paint a detailed and surprisingly rich complexity-theoretic landscape of the problem which includes the identification of paraNP-hard, W[1]-hard and XP-tractable, as well as fixed-parameter tractable fragments of stack layout extension via a natural sequence of parameterizations.
en
dc.description.sponsorship
WWTF Wiener Wissenschafts-, Forschu und Technologiefonds
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
Book Embedding
en
dc.subject
Drawing Extension
en
dc.subject
Parameterized Complexity
en
dc.subject
Stack Layout
en
dc.title
The Parameterized Complexity Of Extending Stack Layouts
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.relation.publication
32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)