The Directed Grid Theorem

DOI10.1145/2746539.2746586zbMath1321.05249arXiv1411.5681OpenAlexW2037750191MaRDI QIDQ2941561

Ken-ichi Kawarabayashi, Stephan Kreutzer

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.5681

zbMATH Keywords

directed graphtree widthgraph structure theorygrid minor

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items (25)

Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Towards the Graph Minor Theorems for Directed Graphs ⋮ Even circuits in oriented matroids ⋮ Constant Congestion Brambles in Directed Graphs ⋮ Frames, $A$-Paths, and the Erdös--Pósa Property ⋮ Disjoint Cycles with Length Constraints in Digraphs of Large Connectivity or Large Minimum Degree ⋮ Constant Congestion Routing of Symmetric Demands in Planar Directed Graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Complete directed minors and chromatic number ⋮ Cut-sufficient directed 2-commodity multiflow topologies ⋮ Detours in directed graphs ⋮ Excluding a planar matching minor in bipartite graphs ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Packing \(A\)-paths of length zero modulo four ⋮ \(k\)-distinct in- and out-branchings in digraphs ⋮ Unnamed Item ⋮ Half-integral linkages in highly connected directed graphs ⋮ Directed Path-Decompositions ⋮ Finding Detours is Fixed-Parameter Tractable ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Subdivisions in digraphs of large out-degree or large dichromatic number ⋮ Euler Digraphs ⋮ Planar Digraphs ⋮ Digraphs of Bounded Width

Uses Software

• Graphs

Cites Work

• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming
• Unnamed Item

This page was built for publication: The Directed Grid Theorem