2025/08/18 by Dobler, Alexander, Holzmüller, Maximilian, Nöllenburg, Martin
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2508.12747
A storyplan visualizes a graph G=(V,E) as a sequence of ℓ frames Γ1, …, Γ_ℓ, each of which is a drawing of the induced subgraph G[Vi] of a vertex subset Vi ⊆ 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.