7 citations · 19 across the 9 of their papers we have counts for
13 papers
Recognition Complexity of Subgraphs of k-Connected Planar Cubic Graphs
Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt
We study the recognition complexity of subgraphs of k-connected planar cubic graphs for k = 1, 2, 3. We present polynomial-time algorithms to recognize subgraphs of 1- and 2-connec…
On the Complexity of Lombardi Graph Drawing
Paul Jungeblut
In a Lombardi drawing of a graph the vertices are drawn as points and the edges are drawn as circular arcs connecting their respective endpoints. Additionally, all vertices have pe…
Cops and Robber -- When Capturing is not Surrounding
Paul Jungeblut, Samuel Schneider, Torsten Ueckerdt
We consider "surrounding" versions of the classic Cops and Robber game. The game is played on a connected graph in which two players, one controlling a number of cops and the other…
Recognizing Unit Disk Graphs in Hyperbolic Geometry is -Complete
Nicholas Bieker, Thomas Bläsius, Emil Dohse +1
A graph G is a (Euclidean) unit disk graph if it is the intersection graph of unit disks in the Euclidean plane . Recognizing them is known to be -…
Primal-Dual Cops and Robber
Minh Tuan Ha, Paul Jungeblut, Torsten Ueckerdt +1
Cops and Robber is a family of two-player games played on graphs in which one player controls a number of cops and the other player controls a robber. In alternating turns, each pl…
Directed Acyclic Outerplanar Graphs Have Constant Stack Number
Paul Jungeblut, Laura Merker, Torsten Ueckerdt
The stack number of a directed acyclic graph is the minimum for which there is a topological ordering of and a -coloring of the edges such that no two edges of the s…
Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
Miriam Goetze, Paul Jungeblut, Torsten Ueckerdt
It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which pl…
Training Fully Connected Neural Networks is -Complete
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut +2
We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalR…
The product structure of squaregraphs
Robert Hickingbotham, Paul Jungeblut, Laura Merker +1
A squaregraph is a plane graph in which each internal face is a -cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to…
The Complexity of the Hausdorff Distance
Paul Jungeblut, Linda Kleist, Tillmann Miltzow
We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algeb…
A Sublinear Bound on the Page Number of Upward Planar Graphs
Paul Jungeblut, Laura Merker, Torsten Ueckerdt
The page number of a directed acyclic graph is the minimum for which there is a topological ordering of and a -coloring of the edges such that no two edges of the sa…
Guarding Quadrangulations and Stacked Triangulations with Edges
Paul Jungeblut, Torsten Ueckerdt
Let be a plane graph. A face of is guarded by an edge if at least one vertex from is on the boundary of . For a planar graph class $\mat…
Multilevel Planarity
Lukas Barth, Guido Brückner, Paul Jungeblut +1
In this paper, we introduce and study the multilevel-planarity testing problem, which is a generalization of upward planarity and level planarity. Let be a directed gr…