2026-07-24T05:11:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25013 2026-02-09T07:53:34Z ddc:004 open_access

Geometry Matters in Planar Storyplans Dobler, Alexander Holzmüller, Maximilian Nöllenburg, Martin geometric storyplan planarity straight-line drawing dynamic graph drawing A storyplan visualizes a graph G = (V,E) as a sequence of 𝓁 frames Γ₁, … , Γ_𝓁, each of which is a drawing of the induced subgraph G[V_i] of a vertex subset V_i ⊆ V. Moreover, each vertex v ∈ V is contained in a single consecutive sequence of frames Γ_i, … , Γ_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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexander Dobler and Maximilian Holzmüller and Martin Nöllenburg 2025 Is Part Of LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2025.27 urn:nbn:de:0030-drops-250135 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.27 eng https://creativecommons.org/licenses/by/4.0/legalcode