55 citations · 188 across the 40 of their papers we have counts for
42 papers · 1 filter
On the -Bend Slope Number of -Planar Graphs
Michael A. Bekos, Eleni Katsanou, Philipp Kindermann +3
While drawing planar graphs with few slopes and few bends is a well-studied problem, corresponding extensions to beyond-planar graphs still remain mostly unexplored. Motivated by t…
On the Recognition of Outerplanar Graphs with Queue Number 1
Michael A. Bekos, Thomas Depian, Stefan Felsner +7
A linear layout of a graph is defined as a total order of the vertices and a partition of the edges to pages. In a stack (queue) layout, no two edges on the same page may cross (ne…
How Many Slopes Does Polynomial Area Cost?
Michael A. Bekos, Eleni Katsanou, Philipp Kindermann +1
In this work, we study the interplay between the number of slopes, the number of bends per edge, and the area requirements for planar drawings of bounded-degree graphs. Our motivat…
Upward-Planar Drawings with Bounded Span
Patrizio Angelini, Sabine Cornelsen, Giordano Da Lozzo +4
We consider upward-planar layered drawings of directed graphs, i.e., crossing-free drawings in which each edge is drawn as a y-monotone curve going upward from its tail to its head…
On the Complexity of Extending Storylines
Alexander Dobler, Siddharth Gupta, Philipp Kindermann +2
Storyline layouts visualize temporal interactions by drawing each character as an x-monotone curve and enforcing that the participants of every meeting form a contiguous vertical g…
Rectangular Duals on the Cylinder and the Torus
Therese Biedl, Philipp Kindermann, Jonathan Klawitter
A rectangular dual of a plane graph is a contact representation of by interior-disjoint rectangles such that (i) no four rectangles share a point, and (ii) the union of all…
Saturated Drawings of Geometric Thickness k
Patricia Bachmann, Anna Brötzner, Miriam Goetze +3
We investigate saturated geometric drawings of graphs with geometric thickness , where no edge can be added without increasing . We establish lower and upper bounds on the nu…
Weakly Leveled Planarity with Bounded Span
Michael Bekos, Giordano Da Lozzo, Fabrizio Frati +5
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 horizonta…
On -Plane Insertion into Plane Drawings
Julia Katheder, Philipp Kindermann, Fabian Klute +2
We introduce the -Plane Insertion into Plane drawing (-PIP) problem: given a plane drawing of a planar graph and a set of edges, insert the edges in into the draw…
Deciding the Feasibility and Minimizing the Height of Tangles
Oksana Firman, Philipp Kindermann, Boris Klemz +3
We study the following combinatorial problem. Given a set of y-monotone \emph{wires}, a \emph{tangle} determines the order of the wires on a number of horizontal \emph{layers}…
Geometric Thickness of Multigraphs is -complete
Henry Förster, Philipp Kindermann, Tillmann Miltzow +3
We say that a (multi)graph has geometric thickness if there exists a straight-line drawing and a -coloring of its edges where no…
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…
Mutual Witness Proximity Drawings of Isomorphic Trees
Carolina Haase, Philipp Kindermann, William J. Lenhart +1
A pair of graphs admits a mutual witness proximity drawing when: (i) represents , and (ii) there is an edge …
Upward and Orthogonal Planarity are W[1]-hard Parameterized by Treewidth
Bart M. P. Jansen, Liana Khazaliya, Philipp Kindermann +3
Upward planarity testing and Rectilinear planarity testing are central problems in graph drawing. It is known that they are both NP-complete, but XP when parameterized by treewidth…
Three Edge-disjoint Plane Spanning Paths in a Point Set
Philipp Kindermann, Jan Kratochvíl, Giuseppe Liotta +1
We consider the following problem: Given a set of distinct points in the plane, how many edge-disjoint plane straight-line spanning paths can be drawn on ? Each spanning…
Splitting Vertices in 2-Layer Graph Drawings
Reyan Ahmed, Patrizio Angelini, Michael A. Bekos +8
Bipartite graphs model the relationships between two disjoint sets of entities in several applications and are naturally drawn as 2-layer graph drawings. In such drawings, the two…
Parameterized Approaches to Orthogonal Compaction
Walter Didimo, Siddharth Gupta, Philipp Kindermann +3
Orthogonal graph drawings are used in applications such as UML diagrams, VLSI layout, cable plans, and metro maps. We focus on drawing planar graphs and assume that we are given an…
Outside-Obstacle Representations with All Vertices on the Outer Face
Oksana Firman, Philipp Kindermann, Jonathan Klawitter +3
An obstacle representation of a graph consists of a set of polygonal obstacles and a drawing of as a visibility graph with respect to the obstacles: vertices are mapped to…
Morphing Rectangular Duals
Steven Chaplick, Philipp Kindermann, Jonathan Klawitter +2
A rectangular dual of a plane graph is a contact representations of by interior-disjoint axis-aligned rectangles such that (i) no four rectangles share a point and (ii) the…
One-Bend Drawings of Outerplanar Graphs Inside Simple Polygons
Patrizio Angelini, Philipp Kindermann, Andre Löffler +2
We consider the problem of drawing an outerplanar graph with vertices with at most one bend per edge if the outer face is already drawn as a simple polygon. We prove that it ca…
Extending Partial Representations of Rectangular Duals with Given Contact Orientations
Steven Chaplick, Philipp Kindermann, Jonathan Klawitter +2
A rectangular dual of a graph is a contact representation of by axis-aligned rectangles such that (i)~no four rectangles share a point and (ii)~the union of all rectangles…
Crossing Numbers of Beyond-Planar Graphs
Markus Chimani, Philipp Kindermann, Fabrizio Montecchiani +1
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 -vertex 1-planar (quas…
Recognizing Stick Graphs with and without Length Constraints
Steven Chaplick, Philipp Kindermann, Andre Löffler +4
Stick graphs are intersection graphs of horizontal and vertical line segments that all touch a line of slope -1 and lie above this line. De Luca et al. [GD'18] considered the recog…
Drawing planar graphs with few segments on a polynomial grid
Philipp Kindermann, Tamara Mchedlidze, Thomas Schneck +1
The visual complexity of a graph drawing can be measured by the number of geometric objects used for the representation of its elements. In this paper, we study planar graph drawin…