10 papers
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…
Towards the Recognition of Oriented Interval Graphs
Lukas P. Bachmann, Jiří Fiala, Miriam Münch +3
Oriented interval graphs, a recent generalization of interval graphs introduced by Gutowski et al. [GD 2022], are intersection graphs of intervals, each of which is oriented either…
Modelling Network Resilience: The Complexity of Some Graph Division Games
Grzegorz Gutowski, Konstanty Junosza-Szaniawski, Antonio Lauerbach +1
Motivated by the controller placement problems in software-defined networks and the fair division principles of classical "cake cutting", we investigate the following two-player ze…
Navigating Posets with Few Maps
Stefan Felsner, Jędrzej Hodor, Giacomo Ortali +1
We study two new parameters for finite posets motivated by the problem of efficiently determining the set of successors of a given element. A plane map of a poset is a…
The Parameterized Complexity of Coloring Mixed Graphs
Antonio Lauerbach, Konstanty Junosza-Szaniawski, Marie Diana Sieper +1
A mixed graph contains (undirected) edges as well as (directed) arcs, thus generalizing undirected and directed graphs. A proper coloring of a mixed graph assigns a positiv…
Bounding the Treewidth of Outer -Planar Graphs via Triangulations
Oksana Firman, Grzegorz Gutowski, Myroslav Kryven +2
The treewidth is a structural parameter that measures the tree-likeness of a graph. Many algorithmic and combinatorial results are expressed in terms of the treewidth. In this pape…
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…
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…
A Simple Pipeline for Orthogonal Graph Drawing
Tim Hegemann, Alexander Wolff
Orthogonal graph drawing has many applications, e.g., for laying out UML diagrams or cableplans. In this paper, we present a new pipeline that draws multigraphs orthogonally, using…