Outerplanar and Forest Storyplans
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911186154422272 |
|---|---|
| author | Fiala, Jiří Firman, Oksana Liotta, Giuseppe Wolff, Alexander Zink, Johannes |
| author_facet | Fiala, Jiří Firman, Oksana Liotta, Giuseppe Wolff, Alexander Zink, Johannes |
| contents | 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. It is known that every graph of treewidth at most 3 admits a planar storyplan and that deciding whether a given graph admits a planar storyplan is NP-complete [Binucci et al., JCSS, 2024].
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 families for which such storyplans do not always exist. In the affirmative case, we present efficient algorithms that produce straight-line storyplans. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_13523 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Outerplanar and Forest Storyplans Fiala, Jiří Firman, Oksana Liotta, Giuseppe Wolff, Alexander Zink, Johannes Computational Geometry Discrete Mathematics 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. It is known that every graph of treewidth at most 3 admits a planar storyplan and that deciding whether a given graph admits a planar storyplan is NP-complete [Binucci et al., JCSS, 2024]. 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 families for which such storyplans do not always exist. In the affirmative case, we present efficient algorithms that produce straight-line storyplans. |
| title | Outerplanar and Forest Storyplans |
| topic | Computational Geometry Discrete Mathematics |
| url | https://arxiv.org/abs/2311.13523 |