Oberseminar "Algorithmen, Komplexität und Mathematische Logik" - Prof. Dr. Meike Hatzel

The first major step towards the graph minor structure theorem by Robertson and Seymour was the grid theorem, a result describing that every graph of large treewidth contains a grid as minor.

In 2014 Wollan gave a definition for a tree-like decomposition and a width parameter tree-cutwidth with respect to immersions, a different graph containment relation. He provided results linking this parameter to immersions of large walls.

This talk presents a version of this parameter for directed graphs, the directed tree-cutwidth. The main result is a grid theorem for directed tree-cutwidth establishing that it is linked to directed immersions of large cylindrical walls.