The Peculiarities of Extending Queue Layouts
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912415627608064 |
|---|---|
| author | Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin |
| author_facet | Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin |
| contents | We consider the problem of computing $\ell$-page queue layouts, which are linear arrangements of vertices accompanied with an assignment of the edges to pages from one to $\ell$ 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 $\ell$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_05156 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Peculiarities of Extending Queue Layouts Depian, Thomas Fink, Simon D. Ganian, Robert Nöllenburg, Martin Computational Geometry Data Structures and Algorithms We consider the problem of computing $\ell$-page queue layouts, which are linear arrangements of vertices accompanied with an assignment of the edges to pages from one to $\ell$ 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 $\ell$-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. |
| title | The Peculiarities of Extending Queue Layouts |
| topic | Computational Geometry Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.05156 |