research
∙
06/05/2023
On the Complexity of Lombardi Graph Drawing
In a Lombardi drawing of a graph the vertices are drawn as points and th...
share
research
∙
02/21/2023
Cops and Robber – When Capturing is not Surrounding
We consider "surrounding" versions of the classic Cops and Robber game. ...
research
∙
01/13/2023
Recognizing Unit Disk Graphs in Hyperbolic Geometry is ∃ℝ-Complete
A graph G is a (Euclidean) unit disk graph if it is the intersection gra...
research
∙
01/13/2023
Primal-Dual Cops and Robber
Cops and Robber is a family of two-player games played on graphs in whic...
research
∙
11/09/2022
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
The stack number of a directed acyclic graph G is the minimum k for whic...
research
∙
04/25/2022
Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
It follows from the work of Tait and the Four-Color-Theorem that a plana...
research
∙
04/04/2022
Training Fully Connected Neural Networks is ∃ℝ-Complete
We consider the algorithmic problem of finding the optimal weights and b...
research
∙
12/08/2021
The Complexity of the Hausdorff Distance
We investigate the computational complexity of computing the Hausdorff d...
research
∙
06/24/2020
Guarding Quadrangulations and Stacked Triangulations with Edges
Let G = (V,E) be a plane graph. A face f of G is guarded by an edge vw ∈...
research
∙
10/31/2018