15 citations · 36 across the 21 of their papers we have counts for
6 papers · 1 filter
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 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…
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…
Planar Steiner Orientation is NP-complete
Moritz Beck, Johannes Blum, Myroslav Kryven +2
Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed graph G (having directed and undirected edge…