The Complexity of Extending Storylines with Minimum Local Crossing Number
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917324877987840 |
|---|---|
| author | Dobler, Alexander Gupta, Siddharth Kindermann, Philipp Montecchiani, Fabrizio Nöllenburg, Martin |
| author_facet | Dobler, Alexander Gupta, Siddharth Kindermann, Philipp Montecchiani, Fabrizio Nöllenburg, Martin |
| contents | Storyline layouts visualize temporal interactions by drawing each character as an $x$-monotone curve and enforcing that the participants of every meeting form a contiguous vertical group. We study a drawing extension variant in which a layout of a sub-storyline is fixed and has to be extended by inserting missing characters while preserving all meeting constraints. We minimize the local crossing number $χ$, i.e., the maximum number of crossings along any single character. We prove that the problem is W[1]-hard parameterized by the number $k$ of inserted characters plus the maximum number $σ$ of active characters, in XP parameterized by $σ$ and in FPT parameterized by $σ+χ$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08340 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Extending Storylines with Minimum Local Crossing Number Dobler, Alexander Gupta, Siddharth Kindermann, Philipp Montecchiani, Fabrizio Nöllenburg, Martin Computational Geometry Storyline layouts visualize temporal interactions by drawing each character as an $x$-monotone curve and enforcing that the participants of every meeting form a contiguous vertical group. We study a drawing extension variant in which a layout of a sub-storyline is fixed and has to be extended by inserting missing characters while preserving all meeting constraints. We minimize the local crossing number $χ$, i.e., the maximum number of crossings along any single character. We prove that the problem is W[1]-hard parameterized by the number $k$ of inserted characters plus the maximum number $σ$ of active characters, in XP parameterized by $σ$ and in FPT parameterized by $σ+χ$. |
| title | The Complexity of Extending Storylines with Minimum Local Crossing Number |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2603.08340 |