Publications 

To appear.

We exploring witness drawings to demonstrate that a graph has bounded pathwidth or treewidth. In our approach, each bag of a tree or path decomposition is shown as a disk featuring a drawing of its induced subgraph, with tracks connecting the same vertices across bags. We propose three drawing styles for the subgraphs inside the bags and their tracks, and provide both exact and heuristic algorithms for computing crossing-minimal layouts. A running prototype is available online.

A stack (queue) layout of a graph consist of a linear arrangement of its vertices and an assignment of its edges to l pages such that no two edges on the same page cross (nest). While these layouts have been extensively studied in the literature, the parameterized complexity of computing them is less understood. In this paper, we give a fixed-parameter algorithm parameterized by the vertex integrity of the graph, that generalizes and unifies earlier algorithms. Furthermore, we provide the first algorithm to compute an l-page width-q layout that avoids a double-exponential dependency on the parameters. Finally, we beat the trivial n^O(n)-time upper bound for computing a 1-page queue layout by presenting an 2^O(n)-time algorithm for this problem.

Motivated by our recent work on extending partial stack layouts, we study how to complete partial l-page queue layouts of a graph—linear arrangements of vertices with edge assignments to l pages that avoid nested edges on each page—and analyze their complexity in detail. Our results give new algorithms, lower bounds, and reveal surprising differences between the extension problem of these two linear layouts.

The geometric thickness of a graph G is the smallest number l such that G admits a single straight-line drawing that can be partitioned into l crossing-free layers. We show that determining the geometric thickness of G is FPT in the vertex cover number and feedback edge set of the graph. Furthermore, we consider the problem of extending a partial drawing of thickness l into a complete one and provide a full classification of its parameterized complexity with respect to the most natural parameters.

In boundary labeling, we place labels along the side of a bounding box and connect each label with its feature using non-crossing leader lines. This is a well-studied external labeling style and efficient algorithms for many settings are known. However, semantic constraints like grouping and ordering have received little attention. We introduce such constraints and analyze the complexity of computing a labeling that adheres to the constraints. We show that the resulting problem is NP-hard in general, but admits polynomial-time algorithms under natural restrictions such as uniform label height or limited placement options. Finally, we experimentally evaluate the performance of one of the algorithms and provide sample labelings. This paper is based on my Master’s Thesis.

An l-page stack layout of a graph is a linear arrangement of its vertices with edges assigned into l pages so that no two edges on the same page cross. Stack layouts are well-studied, and we consider the problem of extending a given partial l-page stack layout into a complete one. We analyze its parameterized complexity under different measures of incompleteness and structural parameters of the input and solution layout. This way, we identify tractable and intractable fragments for this NP-hard problem.

We study the problem of extending a partially pre-colored rectilinear grid such that the total number of corners in the resulting colored shapes is minimized. We show that this problem is NP-hard even for two colors and develop exact algorithms. From the parameterized perspective, we present an FPT- and XP-algorithm in the number of colored cells and solution size.

We study whether a traveler in a public transport network can reach their destination on time despite unexpected delays, modeled as a game between the traveler and a delay-causing adversary and show that this problem is PSPACE-complete.

We initialized the study of transitions between two point labelings and we investigate different types of transitions for labelings of points, most notably consecutive transitions and simultaneous transitions. We give (tight) bounds on the number of overlaps that can occur during these transitions and evaluate them in a prototype implementation. This paper is based on my Bachelor’s Thesis.

In boundary labeling, we place labels along the side of a bounding box and connect each label with its feature using non-crossing leader lines. This is a well-studied external labeling style and efficient algorithms for many settings are known. However, semantic constraints like grouping and ordering have received little attention. We introduce such constraints and analyze the complexity of computing a labeling that adheres to the constraints. We show that the resulting problem is NP-hard in general, but admits polynomial-time algorithms under natural restrictions such as uniform label height or limited placement options. Finally, we experimentally evaluate the performance of one of the algorithms and provide sample labelings. An initial version of this paper has been published at ISAAC’24.

We study the problem of embedding a unit-length path inside a polygonal domain with fixed start and end points, a restricted variant of the known ER-complete linkage realization problem. Despite the simplicity of the input, we show NP-hardness in general and give a polynomial-time algorithm when the path has three edges and the domain is convex.

A level planar drawing is a planar y-monotone drawing where the y-coordinate of each vertex is prescribed by the input. In Partial Level Planarity (PLP), the goal is to extend a given level planar drawing of a subgraph to the full graph while preserving planarity and level constraints. Although PLP is NP-complete even in restricted settings, we identify fixed-parameter tractable fragments by parameterizing the problem by the size of the missing part of the graph.

In my Master’s Thesis, I revisit boundary labeling, a branch of external labeling, where all labels are placed along a rectangular boundary around an illustration. Boundary labelings are a well-studied subject but current algorithms cannot take semantic constraints into account. I introduced grouping and ordering constraints into boundary labeling and analyze the complexity of computing a labeling that adheres to the constraints. In general, the problem is NP-hard but for realistic restrictions (uniform label height or limited placement options), I developed polynomial-time algorithms. I implemented on of these algorithms and used real-world and artificial instances to evaluate its performance.

In my Bachelor’s Thesis, I analyzed labelings of dynamic maps and proposed different ways to visualize changes between two labelings. I defined four goals these so-called transitions should adhere to and proposed three different transition styles. From a theoretical point of view, I showed upper bounds on the number of label overlaps in these transition styles. From the applied perspective, I implemented a prototype and analyzed the transition styles in a practical setting.