%0 Conference Paper
%B Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
%D 2005
%T Algorithmic graph minor theory: Decomposition, approximation, and coloring
%A Demaine,E. D
%A Hajiaghayi, Mohammad T.
%A Kawarabayashi,K.
%K algorithmic graph minor theory
%K approximation algorithm
%K combinatorial polylogarithmic approximation
%K computational complexity
%K constant-factor approximation
%K graph algorithm
%K graph coloring
%K graph colouring
%K half-integral multicommodity flow
%K largest grid minor
%K maximization problem
%K minimization problem
%K polynomial-time algorithm
%K subexponential fixed-parameter algorithm
%K topological graph theory
%K treewidth
%X 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.
%B Foundations of Computer Science, 2005. FOCS 2005. 46th Annual IEEE Symposium on
%P 637 - 646
%8 2005///
%G eng
%R 10.1109/SFCS.2005.14