<div class="csl-bib-body">
<div class="csl-entry">Depian, T., Fink, S. D., Ganian, R., & Nöllenburg, M. (2026). The Peculiarities of Extending Queue Layouts. In H. Fernau & P. Kindermann (Eds.), <i>Graph-Theoretic Concepts in Computer Science : 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers</i> (pp. 177–191). Springer. https://doi.org/10.1007/978-3-032-11835-6_13</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/230307
-
dc.description.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
dc.language.iso
en
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.subject
Extension problems
en
dc.subject
Linear layouts
en
dc.subject
Parameterized complexity
en
dc.subject
Queue layouts
en
dc.title
The Peculiarities of Extending Queue Layouts
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.contributor.editoraffiliation
Universität Trier, Germany
-
dc.contributor.editoraffiliation
Universität Trier, Germany
-
dc.relation.isbn
978-3-032-11835-6
-
dc.relation.doi
10.1007/978-3-032-11835-6
-
dc.description.startpage
177
-
dc.description.endpage
191
-
dc.type.category
Full-Paper Contribution
-
tuw.booktitle
Graph-Theoretic Concepts in Computer Science : 51st International Workshop, WG 2025, Otzenhausen, Germany, June 11–13, 2025, Revised Selected Papers
-
tuw.container.volume
16124
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Cham
-
tuw.researchTopic.id
I1
-
tuw.researchTopic.name
Logic and Computation
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-01 - Forschungsbereich Algorithms and Complexity
-
tuw.publication.orgunit
E056-13 - Fachbereich LogiCS
-
tuw.publisher.doi
10.1007/978-3-032-11835-6_13
-
dc.description.numberOfPages
15
-
tuw.author.orcid
0009-0003-7498-6271
-
tuw.author.orcid
0000-0002-2754-1195
-
tuw.author.orcid
0000-0002-7762-8045
-
tuw.author.orcid
0000-0003-0454-3937
-
tuw.editor.orcid
0000-0002-4444-3220
-
tuw.editor.orcid
0000-0001-5764-7719
-
tuw.event.name
51st International Workshop on Graph-Theoretic Concepts in Computer Science
en
tuw.event.startdate
11-06-2025
-
tuw.event.enddate
13-06-2025
-
tuw.event.online
On Site
-
tuw.event.place
Otzenhausen
-
tuw.event.country
DE
-
tuw.event.presenter
Depian, Thomas
-
wb.sciencebranch
Informatik
-
wb.sciencebranch
Mathematik
-
wb.sciencebranch.oefos
1020
-
wb.sciencebranch.oefos
1010
-
wb.sciencebranch.value
80
-
wb.sciencebranch.value
20
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.grantfulltext
none
-
item.openairetype
conference paper
-
item.languageiso639-1
en
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity
