The Directed Flat Wall Theorem

At the core of the Robertson-Seymour Theory of Graph Minors lies a powerful structure theorem which captures, for any fixed graph H, the common structural features of all the graphs not containing H as a minor [15]. An important step towards this structure theorem is the Flat Wall Theorem [14], which has a lot of algorithmic applications (for example, the minor-testing and the disjoint paths problem with fixed number terminals). In this paper, we prove the directed analogue of this Flat Wall Theorem. Our result builds on the recent Directed Grid Theorem by two of the authors (Kawarabayashi and Kreutzer), and we hope that this is an important and significant step toward the directed structure theorem, as with the case for the undirected graph for the graph minor project.

Authors

• Archontia C. Giannopoulou
• Ken-ichi Kawarabayashi
• Stephan Kreutzer
• O-joung Kwon

Keywords

No keywords are indexed for this paper.