Author: Felix Kainz
Title: Crossing Minimization in One-Sided Time-Interval Storylines with a Protagonist
Supervisor: Prof. Martin Nöllenburg
Assistance: Projektass. Dipl.-Ing. Alexander Dobler
Publishing Date: 2025-10-31
Abstract: Storyline visualizations encode interactions between characters over time, with x-monotone curves representing characters that converge when they interact. However, excessive line crossings quickly reduce readability. This thesis investigates the One-Sided Crossing Minimization in Time Interval Storylines with a Protagonist (1-SCM-TI-P), a variant where one main character remains fixed while interactions within the same temporal group may be reordered freely, as their order is not predetermined. We introduce an exact ILP formulation for crossing minimization together with a fast lower bound and develop a scalable heuristic framework combining a TSP-based initialization with Simu- lated Annealing using structured neighborhood operations. Experiments on real-world research collaboration networks derived from DBLP show that the heuristics achieve near-optimal solutions within milliseconds while the ILP is limited to small or sparse instances. The results demonstrate that high-quality layouts are feasible even for large instances, supporting efficient and readable protagonist-centered storylines in practical applications.
📄 PDF DownloadAuthor: Anna Henriksson
Title: Animating IPE-Presentations
Supervisor: Prof. Martin Nöllenburg
Assistance: Dr. Simon Dominik Fink
Publishing Date: 2025-03-08
Abstract: Presentations are a fundamental part of communicating work progress and results to an audience. This significance can be seen in the vast amount of different programs that can be used to create them. One feature that is present in one of the most generic programs for creating presentations (PowerPoint) is the ability to animate presentations. More specialized programs, such as IPE, do not necessarily provide this feature. Animations do, however, have a number of merits that can help in conveying the content of said presentation. This is why it is worth considering what options there are to add animations to programs that do not inherently support them. This project is based on the premise of supplementing IPE with animations. The here proposed tool ipe_animations provides a means to generate animations for an IPE presentation. This is done by combining the two programs IPE and Manim. This thesis documents the creation of this tool. This begins with an analysis of what its requirements would be. The proposed tool is a combination of two different programs. This means an implementation needs to find or create common ground between those programs. This common ground can be found in the theory of the building blocks of the graphics. Subsequently, an implementation of these requirements is introduced from both a user’s perspective as well as its implementation process. Completing the picture of ipe_animations a short outlook on future work is given.
📄 PDF DownloadAuthor: Sebastian Wodniansky-Wildenfeld
Title: The Left-Right Planarity Test
Supervisor: Prof. Martin Nöllenburg
Assistance: Dr. Simon Dominik Fink
Publishing Date: 2025-02-11
Abstract: Planarity testing is the problem of determining whether a given graph can be drawn in the plane without any edge crossings. It is a fundamental question in graph theory with applications in circuit design, geographic information systems, and network visualization. Several efficient algorithms have been developed for this task, each employing different structural and combinatorial techniques to verify planarity. One such approach is the Left-Right planarity testing method, first introduced by Rosenstiehl and de Fraysseix (1982) and later refined by de Fraysseix, Ossona de Mendez, and Rosenstiehl (2006). Brandes (2008) proposed further simplifications, but their practical efficiency has not been evaluated. This work implements Brandes’ version and systematically compares it to previous implementations and state-of-the-art planarity testing algorithms. The analysis distinguishes between refinements that improve efficiency and those that primarily enhance readability. Through both theoretical and empirical evaluations, this study clarifies the impact of these modifications and assesses the suitability of the Left-Right approach for practical applications.
📄 PDF DownloadAuthor: Simon Niederwolfsgruber
Title: Conformity-Based Area Labeling on Cartographic Maps
Supervisor: Prof. Martin Nöllenburg
Assistance: Dipl.-Ing. Thomas Depian
Publishing Date: 2024-11-30
Abstract: Label placement on maps is a well-known problem in cartography and can be categorized into three major categories: point-, line-, and area labeling. While automated point- and line labeling have been extensively studied and have established formal models, research on automated area labeling remains limited due to the increased complexity in measuring labeling quality. To address this, we present and compare in this thesis, different state of the art approaches. We specifically focus on models that place labels along circular arcs within the boundary polygon and aim to achieve a high degree of conformity, i.e., high similarity of a label with the area it is placed in. As part of this thesis, we propose the HeightConstrained- Labeling problem variant, along with an area labeling pipeline implemented in C++. This pipeline aims to address some of the limitations found in the current literature. In detail, we enhance an established quality function by incorporating additional metrics, then further improve the pipeline through clustering and local search mechanisms. We will also present the results of the implemented pipeline, identify its limitations and discuss potential improvements.
📄 PDF Download