Research
1-Planar Storyplans
Abstract: The field of dynamic graph visualization has received a lot of attention in recent years as new use cases for the exploration of complex graphs have emerged. For example, the representation of vast amounts of relational data as graphs have made a visual analysis more challenging. Storyplans have been introduced as a tool for representing such graphs in a sequential and understandable manner. While planar storyplans as well as outerplanar and forest storyplans have been studied, there has been no research that has gone into the direction of more powerful storyplans such as 1-planar storyplans. This thesis explores the construction of 1-planar storyplans and delves into the specific graph classes that admit these kinds of storyplans. We will extend the strict containment of graph classes that admit storyplans established by Fiala, Firman, Liotta, Wolff, and Zink (SOFSEM 2024) as we explore graphs that do admit 1-planar storyplans but fail to do so for planar storyplans as well as graphs that do not admit 1-planar storyplans. Furthermore, we generalize this graph containment for the graphs that admit p-planar storyplans. We prove that the problem of deciding whether a given graph admits a 1-planar storyplan is NP-hard and we present a parameterized algorithm attempt with respect to the vertex cover number. We conclude the thesis by stating the open problems in this ield. These findings not only enhance our understanding of graph representation through storyplans but also inspire further research.
Download PDF