2005/11/15 by Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken‐ichi Kawarabayashi · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Limits and Structures in Graph Theory #Treewidth #Graph minor #Robertson–Seymour theorem #Graph coloring #Combinatorics #Mathematics #Discrete mathematics #Minor (academic) #1-planar graph #Approximation algorithm #Graph property #Chordal graph #Pathwidth #Voltage graph #Line graph #Graph
paper · doi:10.1109/sfcs.2005.14
openalex publication_date 2005/11/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
At the core of the seminal graph minor theory of Robertson and Seymour is a powerful structural theorem capturing the structure of graphs excluding a fixed minor. This result is used throughout graph theory and graph algorithms, but is existential. We develop a polynomial-time algorithm using topological graph theory to decompose a graph into the structure guaranteed by the theorem: a clique-sum of pieces almost-embeddable into bounded-genus surfaces. This result has many applications. In particular we show applications to developing many approximation algorithms, including a 2-approximation to graph coloring, constant-factor approximations to treewidth and the largest grid minor, combinatorial polylogarithmic approximation to half-integral multicommodity flow, subexponential fixed-parameter algorithms, and PTASs for many minimization and maximization problems, on graphs excluding a fixed minor.