3 papers
cs.DS2025
Cutwidth and Crossings
Johannes Rauch, Dieter Rautenbach
We provide theoretical insights around the cutwidth of a graph and the One-Sided Crossing Minimization (OSCM) problem. OSCM was posed in the Parameterized Algorithms and Computatio…
math.CO2024
Forest Cuts in Sparse Graphs
Vsevolod Chernyshev, Johannes Rauch, Dieter Rautenbach
We propose the conjecture that every graph of order with less than edges has a vertex cut that induces a forest. Maximal planar graphs do not have such vertex cuts a…
math.CO2022
Efficiently recognizing graphs with equal independence and annihilation numbers
Johannes Rauch, Dieter Rautenbach
The annihilation number of a graph is an efficiently computable upper bound on the independence number of . Recently, Hiller observed that a characterization o…