Directed tree-cutwidth links graph width and immersion structure
Potatoes and Onions
Discrete Mathematics
Summary
Graphs are like networks made of points (nodes) connected by lines (edges). To understand complicated graphs, scientists use measures of how 'tree-like' they are. This paper builds on previous work by defining a new way to measure directed graphs called directed tree-cutwidth. The authors show that this measure is closely related to finding certain patterns called large cylindrical walls inside the graph, helping connect different views of graph complexity.
What this means in practice
- •For network analysts: Determine complexity measures in directed networks to guide efficient network decomposition and analysis.
- •For software engineers: Use directed tree-cutwidth concepts to optimize algorithms that handle complex directed data structures.
A theory result. No direct application yet.
Authors
Marcin Briański, Meike Hatzel, Karolina Okrasa, Michał Pilipczuk
Abstract
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.