15 citations · 36 across the 21 of their papers we have counts for
26 papers
Weighted Book Thickness
Henry Förster, Michael Hoffmann, Stephen Kobourov +3
We introduce and study the weighted book thickness of graphs. A -page book embedding of a graph is defined by a spanning cycle for (which does not need to be p…
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…
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…
Simultaneous Embedding of Two Paths on the Grid
Stephen Kobourov, William Lenhart, Giuseppe Liotta +3
Simultaneous geometric embedding of graphs on an integer grid is a classical research topic in Graph Drawing. When the graphs are two paths, one can additionally require that one p…
Unbent Collections of Orthogonal Drawings
Todor Antić, Giuseppe Liotta, Tomáš Masařík +5
Recently, there has been interest in representing single graphs by multiple drawings; for example, using graph stories, storyplans, or uncrossed collections. In this paper, we appl…
Constrained and Ordered Level Planarity Parameterized by the Number of Levels
Václav Blažej, Boris Klemz, Felix Klesen +3
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every e…
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}…
Morphing Graph Drawings in the Presence of Point Obstacles
Oksana Firman, Tim Hegemann, Boris Klemz +4
A crossing-free morph is a continuous deformation between two graph drawings that preserves straight-line pairwise noncrossing edges. Motivated by applications in 3D morphing probl…
Outerplanar and Forest Storyplans
Jiří Fiala, Oksana Firman, Giuseppe Liotta +2
We study the problem of gradually representing a complex graph as a sequence of drawings of small subgraphs whose union is the complex graph. The sequence of drawings is called \em…
Tree Drawings with Columns
Jonathan Klawitter, Johannes Zink
Our goal is to visualize an additional data dimension of a tree with multifaceted data through superimposition on vertical strips, which we call columns. Specifically, we extend up…
Coloring and Recognizing Directed Interval Graphs
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Felix Klesen +3
A \emph{mixed interval graph} is an interval graph that has, for every pair of intersecting intervals, either an arc (directed arbitrarily) or an (undirected) edge. We are particul…
Simultaneous Drawing of Layered Trees
Julia Katheder, Stephen G. Kobourov, Axel Kuckuk +2
We study the crossing-minimization problem in a layered graph drawing of planar-embedded rooted trees whose leaves have a given total order on the first layer, which adheres to the…
Coloring Mixed and Directional Interval Graphs
Grzegorz Gutowski, Florian Mittelstädt, Ignaz Rutter +3
A mixed graph has a set of vertices, a set of undirected egdes, and a set of directed arcs. A proper coloring of a mixed graph is a function that assigns to each vertex in…
The Segment Number: Algorithms and Universal Lower Bounds for Some Classes of Planar Graphs
Ina Goeßmann, Jonathan Klawitter, Boris Klemz +5
The segment number of a planar graph is the smallest number of line segments needed for a planar straight-line drawing of . Dujmović, Eppstein, Suderman, and Wood [CGTA'07]…
Polyline Simplification under the Local Fréchet Distance has Almost-Quadratic Runtime in 2D
Sabine Storandt, Johannes Zink
Given a polyline on vertices, the polyline simplification problem asks for a minimum size subsequence of these vertices defining a new polyline whose distance to the original p…
Consistent Simplification of Polyline Tree Bundles
Yannick Bosch, Peter Schäfer, Joachim Spoerhase +2
The Polyline Bundle Simplification (PBS) problem is a generalization of the classical polyline simplification problem. Given a set of polylines, which may share line segments and p…
Upward Planar Drawings with Three and More Slopes
Jonathan Klawitter, Johannes Zink
The slope number of a graph is the smallest number of slopes needed for the segments representing the edges in any straight-line drawing of . It serves as a measure of the v…
Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
Martin Koutecký, Johannes Zink
The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector, are among the oldest and most funda…
Erratum: Fast and Simple Horizontal Coordinate Assignment
Ulrik Brandes, Julian Walter, Johannes Zink
We point out two flaws in the algorithm of Brandes and Köpf (Proc. GD 2001), which is often used for the horizontal coordinate assignment in Sugiyama's framework for layered layout…
Layered Drawing of Undirected Graphs with Generalized Port Constraints
Johannes Zink, Julian Walter, Joachim Baumeister +1
The aim of this research is a practical method to draw cable plans of complex machines. Such plans consist of electronic components and cables connecting specific ports of the comp…
The Complexity of Finding Tangles
Oksana Firman, Philipp Kindermann, Boris Klemz +3
We study the following combinatorial problem. Given a set of y-monotone curves, which we call wires, a tangle determines the order of the wires on a number of horizontal layers…
Simplification of Polyline Bundles
Joachim Spoerhase, Sabine Storandt, Johannes Zink
We propose and study a generalization to the well-known problem of polyline simplification. Instead of a single polyline, we are given a set of polylines possibly sharing so…
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…
Computing Height-Optimal Tangles Faster
Oksana Firman, Philipp Kindermann, Alexander Ravsky +2
We study the following combinatorial problem. Given a set of y-monotone wires, a tangle determines the order of the wires on a number of horizontal layers such that the orders…