Philipp Kindermann

TCS Journal 2026 Journal Article

Weakly leveled planarity with bounded span

• Michael A. Bekos
• Giordano Da Lozzo
• Fabrizio Frati
• Siddharth Gupta
• Philipp Kindermann
• Giuseppe Liotta
• Ignaz Rutter
• Ioannis G. Tollis

This paper studies planar drawings of graphs in which each vertex is represented as a point along a sequence of horizontal lines, called levels, and each edge is either a horizontal segment or a strictly y-monotone curve. A graph is s-span weakly leveled planar if it admits such a drawing where the edges have span at most s; the span of an edge is the number of levels it touches minus one. We investigate the problem of computing s-span weakly leveled planar drawings from both the computational and the combinatorial perspectives. We prove the problem to be para-NP-hard with respect to its natural parameter s and investigate its complexity with respect to widely used structural parameters. We show the existence of a polynomial-size kernel with respect to vertex cover number and prove that the problem is FPT when parameterized by treedepth. We also present upper and lower bounds on the span for various graph classes. Notably, we show that cycle trees, a family of 2-outerplanar graphs generalizing Halin graphs, are Θ(log n)-span weakly leveled planar and 4-span weakly leveled planar when 3-connected. As a byproduct of these combinatorial results, we obtain improved bounds on the edge-length ratio of the graph families under consideration.

TCS Journal 2025 Journal Article

On layered area-proportional rectangle contact representations

• Carolina Haase
• Philipp Kindermann

Semantic word clouds visualize the semantic relatedness between the words of a text by placing pairs of related words close to each other. Formally, the problem of drawing semantic word clouds corresponds to drawing a rectangle contact representation of a graph whose vertices correlate to the words to be displayed and whose edges indicate that two words are semantically related. The goal is to maximize the number of realized contacts while avoiding any false adjacencies. We consider a variant of this problem that restricts input graphs to be layered and all rectangles to be of equal height, called Maximum Layered Contact Representation Of Word Networks or Max-LayeredCrown, as well as the variant Max-IntLayeredCrown, which restricts the problem to only rectangles of integer width and the placement of those rectangles to integer coordinates. We classify the corresponding decision problem k-IntLayeredCrown as NP-complete even for internally triangulated planar graphs and k-LayeredCrown as NP-complete for planar graphs. We introduce three algorithms: a 1/2-approximation for Max-LayeredCrown of internally triangulated planar graphs, and a PTAS and an XP algorithm for Max-IntLayeredCrown with rectangle width polynomial in n.

TCS Journal 2022 Journal Article

Crossing numbers of beyond-planar graphs

• Markus Chimani
• Philipp Kindermann
• Fabrizio Montecchiani
• Pavel Valtr

We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are n-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has Ω ( n ) crossings, while O ( 1 ) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.

TCS Journal 2022 Journal Article

On mixed linear layouts of series-parallel graphs

• Patrizio Angelini
• Michael A. Bekos
• Philipp Kindermann
• Tamara Mchedlidze

A mixed s-stack q-queue layout of a graph consists of a linear order of its vertices and a partition of its edges into s stacks and q queues, such that no two edges in the same stack cross and no two edges in the same queue nest. In 1992, Heath and Rosenberg conjectured that every planar graph admits a mixed 1-stack 1-queue layout. In 2017, Pupyrev disproved this conjecture by demonstrating a planar partial 3-tree that does not admit a mixed 1-stack 1-queue layout. In this work, we strengthen Pupyrev's result by showing that the conjecture does not hold even for 2-trees, also known as series-parallel graphs. We conclude this by means of a stronger result, stating that the conjecture does not hold, even in the more general union and local settings. In the former, crossings (nestings) are allowed in the stack (queue) as long as the involved edges belong to different connected components of the subgraph induced by its edges, while in the latter several stacks and queues may form the layout, but locally every vertex is incident to edges from only one stack and one queue.

TCS Journal 2022 Journal Article

Simple algorithms for partial and simultaneous rectangular duals with given contact orientations

• Steven Chaplick
• Stefan Felsner
• Philipp Kindermann
• Jonathan Klawitter
• Ignaz Rutter
• Alexander Wolff

A rectangular dual of a graph G is a contact representation of G by axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the union of all rectangles is a rectangle. The partial representation extension problem for rectangular duals asks whether a given partial rectangular dual can be extended to a rectangular dual, that is, whether there exists a rectangular dual where some vertices are represented by prescribed rectangles. The simultaneous representation problem for rectangular duals asks whether two (or more) given graphs that share a subgraph admit rectangular duals that coincide on the shared subgraph. Combinatorially, a rectangular dual can be described by a regular edge labeling (REL), which determines the orientations of the rectangle contacts. We describe linear-time algorithms for the partial representation extension problem and the simultaneous representation problem for rectangular duals when each input graph is given together with a REL. Both algorithms are based on formulations as linear programs, yet they have geometric interpretations and can be seen as extensions of the classic algorithm by Kant and He that computes a rectangular dual for a given graph.

TCS Journal 2019 Journal Article

Greedy rectilinear drawings

• Patrizio Angelini
• Michael A. Bekos
• Walter Didimo
• Luca Grilli
• Philipp Kindermann
• Tamara Mchedlidze
• Roman Prutkin
• Antonios Symvonis

A drawing of a graph is greedy if for each ordered pair of vertices u and v, there is a path from u to v such that the Euclidean distance to v decreases monotonically at every vertex of the path. From an application perspective, greedy drawings are especially relevant to support routing schemes in ad hoc wireless networks. The existence of greedy drawings has been widely studied under different topological and geometric constraints, such as planarity, face convexity, and drawing succinctness. We introduce greedy rectilinear drawings, where edges are horizontal or vertical segments. These drawings have several properties that improve human readability and support network routing. We address the problem of testing whether a planar rectilinear representation, i. e. , a plane graph with prescribed vertex angles, admits a greedy rectilinear drawing. We give a characterization, a linear-time testing algorithm, and a full generative scheme for universal greedy rectilinear representations, i. e. , those for which every drawing is greedy. For general greedy rectilinear representations, we give a combinatorial characterization and, based on it, a polynomial-time testing and drawing algorithm for a meaningful subset of instances.

TCS Journal 2018 Journal Article

1-Fan-bundle-planar drawings of graphs

• Patrizio Angelini
• Michael A. Bekos
• Michael Kaufmann
• Philipp Kindermann
• Thomas Schneck

Edge bundling is an important concept, heavily used for graph visualization purposes. To enable the comparison with other established nearly-planarity models in graph drawing, we formulate a new edge-bundling model which is inspired by the recently introduced fan-planar graphs. In particular, we restrict the bundling to the end segments of the edges. Similarly to 1-planarity, we call our model 1-fan-bundle-planarity, as we allow at most one crossing per bundle. For the two variants where we allow either one or, more naturally, both end segments of each edge to be part of bundles, we present edge density results and consider various recognition questions, not only for general graphs, but also for the outer and 2-layer variants. We conclude with a series of challenging questions.

TCS Journal 2016 Journal Article

Recognizing and drawing IC-planar graphs

• Franz J. Brandenburg
• Walter Didimo
• William S. Evans
• Philipp Kindermann
• Giuseppe Liotta
• Fabrizio Montecchiani

We give new results about the relationship between 1-planar graphs and RAC graphs. A graph is 1-planar if it has a drawing where each edge is crossed at most once. A graph is RAC if it can be drawn in such a way that its edges cross only at right angles. These two classes of graphs and their relationships have been widely investigated in the last years, due to their relevance in application domains where computing readable graph layouts is important to analyze or design relational data sets. We study IC-planar graphs, the sub-family of 1-planar graphs that admit 1-planar drawings with independent crossings (i. e. , no two crossed edges share an endpoint). We prove that every IC-planar graph admits a straight-line RAC drawing, which may require however exponential area. If we do not require right angle crossings, we can draw every IC-planar graph with straight-line edges in linear time and quadratic area. We then study the problem of testing whether a graph is IC-planar. We prove that this problem is NP-hard, even if a rotation system for the graph is fixed. On the positive side, we describe a polynomial-time algorithm that tests whether a triangulated plane graph augmented with a given set of edges that form a matching is IC-planar.

SODA Conference 2016 Conference Paper

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

• Patrizio Angelini
• Giordano Da Lozzo
• Giuseppe Di Battista
• Valentino Di Donato
• Philipp Kindermann
• Günter Rote
• Ignaz Rutter