Minimizing wiggles in storyline visualizations

Abstract

Storyline Visualizations sind einfache 2-dimensionale Illustrationen über die Handlungen von Filmen oder Büchern die nur aus den horizontal verlaufenden Lebenslinien der Charaktere der Geschichte und den Interaktionen der einzelnen Charaktere miteinander bestehen. Diese Interaktionen stehen im Fokus einer Storyline Visualization. Aktuelle wissenschaftliche Arbeiten haben ihren Fokus auf der Optimierung von Storyline Visualizations durch die Minimierung von Kreuzungen zwischen den Linien der Charaktere. Diese Diplomarbeit knüpft an diese Vorarbeit an und behandelt vertikale Sprünge entlang der Charakterlinien. Solche Höhensprünge werden im Zusammenhand mit Storyline Visualizations als Wiggles bezeichnet. Ziel ist es die Qualität und Lesbarkeit von Storyline Visualizations zu verbessert indem Wiggles minimiert werden. Um diese Wiggles zu reduzieren werden zuerst Optimierungs-Metriken definiert, um die Qualität einer Storyline Visualization in Zahlen ausdrücken zu können. Insgesamt haben wir vier solcher Metriken: die Gesamthöhe aller Wiggles (total wiggle height), die Anzahl aller Wiggles (number of wiggles), die Höhe des höchsten Wiggles (highest wiggle) und die Anzahl aller paarweisen Kreuzungen (number of pairwise crossings). Diese Metriken bilden die Grundlage für die Zielfunktionen von Wiggle-Minimierungen. Mit einer kombinatorischen Sichtweise auf unser Optimierungsproblem beschreibt diese Arbeit zwei Lösungsmodelle um die vertikale Anordnung der Charakterlinien für jeden Zeitpunkt zu variieren um die beste Lösung mit den kleinsten möglichen Werten für unsere Metriken zu produzieren. Das erste Modell beschreibt ein ganzzahliges lineares Programm (ILP) für Wiggle-Minimierung, das zweite Modell beinhaltet die Formulierung eines maximalen Erfüllbarkeitsproblems (Max-SAT) zur Wiggle-Minimierung. Basierend auf unseren beiden Lösungsmodellen wurden Experimente durchgeführt um die unterschiedlichen Variationen der möglichen Zielfunktionen bezüglich Wiggle-Minimierung auszutesten. Die Evaluierung dieser Experimente zeigt deutlich, dass die Minimierung der Gesamthöhe aller Wiggles die besten Resultate bezüglich unserer Metriken erzielt. Die Minimierung von Wiggles reduziert auch die Anzahl der Kreuzungen innerhalb einer Storyline Visualization. Durch eine kombinierte Optimierung von Wiggles und Kreuzungen kann die Anzahl der Kreuzungen weiter reduziert werden, allerdings meist auf Kosten der anderen Wiggle-Metriken.

Storyline visualizations are abstract 2-dimensional drawings of storylines, which shows the lifelines of the characters of the storyline as horizontal lines and interactions between those characters by bundles of the corresponding character lines. The focus lies on illustrating the interactions of the characters within the storyline. Recent scientific work had its focus on optimizing storyline visualizations by minimizing crossings. This thesis examines line wiggles as another important quality criteria of storyline visualizations and how such wiggles can be minimized to generate storyline visualizations with good legibility. To minimize wiggles we start defining optimization metrics for total wiggle height, number of wiggles, highest wiggle and number of pairwise crossings which can be used to formulate objective functions for optimizations of storyline visualizations. Considering our optimization problem as a combinatorial problem we formulate two solution models for optimizing storyline visualizations based on changing the vertical order of the character lines to minimize one or more of our optimization metrics. The first solution model contains an Integer Linear Programming (ILP) approach; the second solution model describes a Max-SAT formulation. Following experiments based on our two solution models with different objective formulations show that the minimization of the total wiggle height produces the best results regarding our four optimization metrics and that wiggle minimizations also reduces crossing within a storyline visualization. With multi-objectives for combined minimization of wiggles and crossings the number of crossings can be further reduced, but very likely at the expense of at least one of the wiggle metric values.