Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces directed tree-cutwidth, a new parameter for directed graphs analogous to Wollan's tree-cutwidth for undirected graphs. The authors prove a grid theorem for this new parameter, establishing its duality with directed immersions of large cylindrical walls. This result extends the theory of graph minors and width parameters to the directed graph setting, specifically concerning immersions.
Directed graphs with high directed tree-cutwidth must contain large directed cylindrical walls as immersions, mirroring Wollan's result for undirected graphs and immersions.
The first major step in the theory of graph minors of Robertson and Seymour was the grid theorem, a fundamental duality result describing that any graph of sufficiently high treewidth must contain a large grid as a minor. Since this pioneering work, multiple grid theorems have been established in structural graph theory, linking various width parameters of combinatorial objects with the non-existence of grid-like obstructions. In particular, Kawarabayashi and Kreutzer [STOC'15] proved a variant of the grid theorem for directed graphs that links directed treewidth with the non-existence of topological minors of large cylindrical walls. On the other hand, to study immersions of undirected graphs $-$ another containment relation that focuses on edge-disjointness, rather than vertex-disjointness $-$ Wollan [JCTB'15] introduced a parameter, tree-cutwidth, and proved that it is dual to immersions of large walls. In this work, we present a version of Wollan's parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth, establishing that it is dual to directed immersions of large cylindrical walls.