3 papers
math.CO2025
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…
cs.DM2024
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…
math.CO2024
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…