5 papers
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…
Cops and Robbers on 1-Planar Graphs
Stephane Durocher, Shahin Kamali, Myroslav Kryven +6
Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and robber move along edges of G. The cop number of…
Drawing Graphs with Circular Arcs and Right-Angle Crossings
Steven Chaplick, Henry Förster, Myroslav Kryven +1
In a RAC drawing of a graph, vertices are represented by points in the plane, adjacent vertices are connected by line segments, and crossings must form right angles. Graphs that ad…
On Arrangements of Orthogonal Circles
Steven Chaplick, Henry Förster, Myroslav Kryven +1
In this paper, we study arrangements of orthogonal circles, that is, arrangements of circles where every pair of circles must either be disjoint or intersect at a right angle. Usin…
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…