Outerplanar and Forest Storyplans
arXiv:2311.13523
Abstract
We study the problem of gradually representing a complex graph as a sequence of drawings of small subgraphs whose union is the complex graph. The sequence of drawings is called \emph{storyplan}, and each drawing in the sequence is called a \emph{frame}. In an (outer)planar storyplan, every frame is (outer)planar; in a forest storyplan, every frame is acyclic. Binucci, Di Giacomo, Lenhart, Liotta, Montecchiani, Nöllenburg, and Symvonis [JCSS 2024] proved that every graph of treewidth at most 3 admits a planar storyplan and that deciding whether a given graph admits a \emph{planar} storyplan is NP-complete. They also presented two FPT algorithms, one parameterized with respect to the vertex cover number and one with respect to the feedback edge set number of the input graph. We first prove that deciding whether a given graph admits an outerplanar storyplan (or a forest storyplan) is NP-complete. Then, we show that the FPT algorithms of Binucci et al. also work for our problem variants with small modifications. We identify graph families that admit outerplanar and forest storyplans and graph families for which such storyplans do not always exist. In the affirmative case, we present efficient algorithms that produce storyplans with straight-line edges.
An earlier version of this paper has appeared in Proc. SOFSEM 2024