<div class="csl-bib-body">
<div class="csl-entry">Binucci, C., Di Giacomo, E., Lenhart, W., Liotta, G., Montecchiani, F., Nöllenburg, M., & Symvonis, A. (2024). On the complexity of the storyplan problem. <i>Journal of Computer and System Sciences</i>, <i>139</i>, Article 103466. https://doi.org/10.1016/j.jcss.2023.103466</div>
</div>
-
dc.identifier.issn
0022-0000
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/190635
-
dc.description.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.
