Binucci, C., Di Giacomo, E., Lenhart, W., Liotta, G., Montecchiani, F., Nöllenburg, M., & Symvonis, A. (2024). On the complexity of the storyplan problem. Journal of Computer and System Sciences, 139, Article 103466. https://doi.org/10.1016/j.jcss.2023.103466
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.
CC BY 4.0
