Expanding the Planar Storyplan Problem

Abstract

Diese Diplomarbeit untersucht Methoden zur Verbesserung des Verständnisses komplexer Graphen durch die Einführung neuer Varianten des Storyplan Problems.Es werden das Planare Geometrische Storyplan, das Planare Topologische k-StoryPlan, das Planare Geometrische k-StoryPlan, das Minimale Planare Topologische StoryPlan und das Minimale Planare Geometrische StoryPlan Problem untersucht, wobei die NP-Schwere all dieser Probleme nachgewiesen wird. Ein Storyplan ist eine Methode, welche einen Graphen G = (V, E) in mehrere Frames aufteilt, sodass jedes einen induzierten Teilgraphen von G repräsentiert. Die Frames sind chronologisch angeordnet, wobei in jedem Frame ein neuer Knoten erscheint. Diese Praxis erleichtert das Verständnis der Graphen, indem diese in kleinere, überschaubare Teile zerlegt werden. Allerdings ist das Aufteilen in mehrere Teilgraphen nicht ausreichend. Jedes Frame muss auch einfach zu interpretieren sein. Das motiviert die Entwicklung neuer Varianten des Storyplan Problems. Unsere Arbeit baut auf der Forschung von Binucci et al. auf. Diese haben das Planare Topologische StoryPlan Problem (PTOP-SP) eingeführt, wo jedes Frame eine planare Zeichnung sein muss und alle Kanten als Jordankurven dargestellt werden. Wir erweitern diese Grundlage durch die Einführung fünf neuer Varianten. Beim Planaren Geometrischen StoryPlan Problem (PGEO-SP) muss die Zeichnung jedes Frames planar sein und alle Kanten müssen geradlinig dargestellt werden, um für ein besseres Verständnis der einzelnen Frames zu sorgen. Das Planare Topologische k-StoryPlan Problem (PTOP-k-SP) und das Planaren Geometrischen k-StoryPlan Problem (PGEO-k-SP) haben die selben Einschränkungen für die Zeichnungen der einzelnen Frames wie PTOP-SP und PGEO-SP, erlauben jedoch, dass mehrere Knoten in einem Frame auftauchen dürfen, um die Gesamtanzahl der benötigten Frames zu reduzieren. Das Minimale Planare Topologische StoryPlan Problem (MIN-PTOP-SP) und das Minimale Planaren Geometrischen StoryPlan Problem (MIN-PGEO-SP) wollen die Anzahl der Frames minimieren, um jeweils den kleinstmöglichen planaren topologischen beziehungsweise planaren geometrischen Storyplan zu erhalten. Der Hauptbeitrag dieser Arbeit ist ein Beweis durch Gegenbeispiel, dass PGEO-SP und PTOP-SP zwei distinkte Probleme sind. Weiters zeigen wir, dass alle fünf Probleme NP-schwer sind und PTO-k-SP sogar NP-vollständig ist.

This thesis investigates methods for improving the comprehension of complex graphs by introducing new variations of the storyplan problem. We explore the Planar Geometric Storyplan, the Planar Topological k-StoryPlan, the Planar Geometric k-StoryPlan, the Minimal Planar Topological StoryPlan, and the Minimal Planar Geometric StoryPlan problems, providing novel insights into graph representation and establishing the NP-hardness of each of these problems. A storyplan is a technique in which a complex graph G = (V, E) is split into multiple frames, each representing an induced subgraph of G. The frames are ordered chronologically, with one new vertex appearing in each frame. This process helps simplify graph comprehension by breaking it into smaller, more manageable parts. However, simply dividing the graph into subgraphs may not be sufficient. Each frame must also be easy to interpret, which motivates the development of new variations of the storyplan problem. We build on the work of Binucci et al., who introduced the Planar Topological StoryPlan problem (PTOP-SP), where each frame must be a planar drawing and all edges are represented by Jordan arcs. Our contributions expand on this foundation by proposing five novel variations. In the Planar Geometric StoryPlan problem (PGEO-SP), the drawing of each frame must be planar, and all edges must be embedded as straight-lines for better clarity of the single frames. The Planar Topological k-StoryPlan problem (PTOP-k-SP) and the Planar Geometric k-StoryPlan problem (PGEO-k-SP) have the same restrictions on the embedding of each frame as PTOP-SP and PGEO-SP, respectively, but allow multiple vertices to appear in the same frame to reduce the total number of frames needed. The Minimal Planar Topological StoryPlan problem (MIN-PTOP-SP) and the Minimal Planar Geometric StoryPlan problem (MIN-PGEO-SP) seek to minimize the number of frames to obtain the smallest possible planar topological or planar geometric storyplan, respectively. The main contribution of this thesis is a proof by counterexample showing that PGEO-SP is distinct from PTOP-SP. We then prove that PGEO-SP is NP-hard. In addition, we show that PTOP-k-SP is NP-complete and PGEO-k-SP is NP-hard, for general values of k. Finally, we demonstrate that the minimization variants MIN-PTOP-SP and MIN-PGEO-SP are NP-hard.