5 papers
How Close is a Tree to a Euclidean Minimum Spanning Tree?
Todor AntiÄ, JiÅà Fiala, Jelena GliÅ¡iÄ +8
Let be a straight-line crossing-free drawing of a tree . A \emph{bad pair} in is a pair of non-adjacent vertices of whose Euclidean distance in is smaller tha…
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…
One-Sided Local Crossing Minimization
Panos Giannopoulos, Miriam Goetze, Grzegorz Gutowski +6
Drawing graphs with the minimum number of crossings is a classical problem that has been studied extensively. Many restricted versions of the problem have been considered. For exam…
A Note on the Complexity of Defensive Domination
Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk
In a graph G, a k-attack A is any set of at most k vertices and l-defense D is a set of at most l vertices. We say that defense D counters attack A if each a in A can be matched to…
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…