6 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…