Record link: 
http://hdl.handle.net/20.500.12708/230307
-
Title: 
The Peculiarities of Extending Queue Layouts
en
Citation: 
Depian, T., Fink, S. D., Ganian, R., & Nöllenburg, M. (2026). The Peculiarities of Extending Queue Layouts. In H. Fernau & P. Kindermann (Eds.), Graph-Theoretic Concepts in Computer Science : 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers (pp. 177–191). Springer. https://doi.org/10.1007/978-3-032-11835-6_13
-
Publisher DOI: 
10.1007/978-3-032-11835-6_13
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Depian, Thomas 
Fink, Simon D. 
Ganian, Robert 
Nöllenburg, Martin 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
E056-13 - Fachbereich LogiCS 
-
Published in: 
Graph-Theoretic Concepts in Computer Science : 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers 
-
ISBN: 
978-3-032-11835-6
-
Volume: 
16124
-
DOI of the book: 
10.1007/978-3-032-11835-6
-
Date (published): 
2-Jan-2026
-
Event name: 
51st International Workshop on Graph-Theoretic Concepts in Computer Science 
en
Event date: 
11-Jun-2025 - 13-Jun-2025
-
Event place: 
Otzenhausen, Germany
-
Number of Pages: 
15
-
Publisher: 
Springer, Cham
-
Peer reviewed: 
Yes
-
Keywords: 
Extension problems; Linear layouts; Parameterized complexity; Queue layouts
en
Abstract: 
We consider the problem of computing ℓ-page queue layouts, which are linear arrangements of vertices accompanied with an assignment of the edges to pages from one to ℓ that avoid the nesting of edges on any of the pages. Inspired by previous work in the extension of stack layouts, here we consider the setting of extending a partial ℓ-page queue layout into a complete one and primarily analyze the problem through the refined lens of parameterized complexity. We obtain novel algorithms and lower bounds which provide a detailed picture of the problem’s complexity under various measures of incompleteness, and identify surprising distinctions between queue and stack layouts in the extension setting.
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

9
checked on Aug 25, 2026

Google ScholarTM

Check