On the complexity of the storyplan problem

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 NPcomplete if the vertex appearance order is given and we have to choose how to draw the frames. (c) 2023 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).

Automated summary

In this study, we investigate the problem of representing a graph as a storyplan, which is a model for dynamic graph visualization. We prove the NP-completeness of this problem and propose two parameterized algorithms as solutions. We also demonstrate that partial 3-trees always admit a storyplan and can be computed in linear time. Additionally, we show that even if the vertex appearance order is given, the problem of choosing how to draw the frames remains NP-complete.