Showing 2025Show all
3 papers · 1 filter
cs.DM2025
Well-Quasi-Ordering Eulerian Digraphs Embeddable in Surfaces by Strong Immersion
Dario Cavallaro, Ken-ichi Kawarabayashi, Stephan Kreutzer
We prove that for every surface , the class of Eulerian directed graphs that are Eulerian embeddable into (in particular they have degree at most ) is well-quasi-ordered…
cs.DM2025
The Directed Disjoint Paths Problem with Congestion
Matthias Bentert, Dario Cavallaro, Amelie Heindl +3
The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-kn…
math.CO2025
Directed treewidth is closed under taking butterfly minors
Gunwoo Kim, Meike Hatzel, Stephan Kreutzer
Butterfly minors are a generalisation of the minor containment relation for undirected graphs to directed graphs. Many results in directed structural graph theory use this notion a…