Geometry Matters in Planar Storyplans
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908493041106944 |
|---|---|
| author | Dobler, Alexander Holzmüller, Maximilian Nöllenburg, Martin |
| author_facet | Dobler, Alexander Holzmüller, Maximilian Nöllenburg, Martin |
| contents | A storyplan visualizes a graph $G=(V,E)$ as a sequence of $\ell$ frames $Γ_1, \dots, Γ_\ell$, each of which is a drawing of the induced subgraph $G[V_i]$ of a vertex subset $V_i \subseteq V$. Moreover, each vertex $v \in V$ is contained in a single consecutive sequence of frames $Γ_i, \dots, Γ_j$, all vertices and edges contained in consecutive frames are drawn identically, and the union of all frames is a drawing of $G$. In GD 2022, the concept of planar storyplans was introduced, in which each frame must be a planar (topological) drawing. Several (parameterized) complexity results for recognizing graphs that admit a planar storyplan were provided, including NP-hardness. In this paper, we investigate an open question posed in the GD paper and show that the geometric and topological settings of the planar storyplan problem differ: We provide an instance of a graph that admits a planar storyplan, but no planar geometric storyplan, in which each frame is a planar straight-line drawing. Still, by adapting the reduction proof from the topological to the geometric setting, we show that recognizing the graphs that admit planar geometric storyplans remains NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_12747 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Geometry Matters in Planar Storyplans Dobler, Alexander Holzmüller, Maximilian Nöllenburg, Martin Computational Complexity A storyplan visualizes a graph $G=(V,E)$ as a sequence of $\ell$ frames $Γ_1, \dots, Γ_\ell$, each of which is a drawing of the induced subgraph $G[V_i]$ of a vertex subset $V_i \subseteq V$. Moreover, each vertex $v \in V$ is contained in a single consecutive sequence of frames $Γ_i, \dots, Γ_j$, all vertices and edges contained in consecutive frames are drawn identically, and the union of all frames is a drawing of $G$. In GD 2022, the concept of planar storyplans was introduced, in which each frame must be a planar (topological) drawing. Several (parameterized) complexity results for recognizing graphs that admit a planar storyplan were provided, including NP-hardness. In this paper, we investigate an open question posed in the GD paper and show that the geometric and topological settings of the planar storyplan problem differ: We provide an instance of a graph that admits a planar storyplan, but no planar geometric storyplan, in which each frame is a planar straight-line drawing. Still, by adapting the reduction proof from the topological to the geometric setting, we show that recognizing the graphs that admit planar geometric storyplans remains NP-hard. |
| title | Geometry Matters in Planar Storyplans |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2508.12747 |