1. On the complexity of the storyplan problem.
- Author
-
Binucci, Carla, Di Giacomo, Emilio, Lenhart, William J., Liotta, Giuseppe, Montecchiani, Fabrizio, Nöllenburg, Martin, and Symvonis, Antonios
- Subjects
- *
DATA visualization , *DYNAMIC models - Abstract
We study the problem of representing a graph as a storyplan, a recently introduced model for dynamic graph visualization. It is based on a sequence of frames, each showing a subset of vertices and a planar drawing of their induced subgraphs, where vertices appear and disappear over time. Namely, in the StoryPlan problem, we are given a graph and we want to decide whether there exists a total vertex appearance order for which a storyplan exists. We prove that the problem is NP -complete, and complement this hardness with two parameterized algorithms, one in the vertex cover number and one in the feedback edge set number of the input graph. We prove that partial 3-trees always admit a storyplan, which can be computed in linear time. Finally, we show that the problem remains NP -complete if the vertex appearance order is given and we have to choose how to draw the frames. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF