**Reference**:- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction”,
*Algorithmica*, volume 54, number 2, June 2009, pages 142–180. Special issue of selected papers from the 17th Annual International Symposium on Algorithms and Computation, 2006. **Abstract**:-
We explore three important avenues of research in algorithmic graph-minor
theory, which all stem from a key min-max relation between the treewidth of a
graph and its largest grid minor. This min-max relation is a keystone of the
Graph Minor Theory of Robertson and Seymour, which ultimately proves Wagner's
Conjecture about the structure of minor-closed graph properties.
First, we obtain the only known polynomial min-max relation for graphs that do not exclude any fixed minor, namely, map graphs and power graphs. Second, we obtain explicit (and improved) bounds on the min-max relation for an important class of graphs excluding a minor, namely,

*K*_{3, k}-minor-free graphs, using new techniques that do not rely on Graph Minor Theory. These two avenues lead to faster fixed-parameter algorithms for two families of graph problems, called minor-bidimensional and contraction-bidimensional parameters, which include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex-removal parameters, dominating set, edge dominating set,*R*-dominating set, connected dominating set, connected edge dominating set, connected*R*-dominating set, and unweighted TSP tour. Third, we disprove a variation of Wagner's Conjecture for the case of graph contractions in general graphs, and in a sense characterize which graphs satisfy the variation. This result demonstrates the limitations of a general theory of algorithms for the family of contraction-closed problems (which includes, for example, the celebrated dominating-set problem). If this conjecture had been true, we would have had an extremely powerful tool for proving the existence of efficient algorithms for any contraction-closed problem, like we do for minor-closed problems via Graph Minor Theory. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Availability**:- The paper is available in PostScript (846k) and PDF (462k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GridWagner_ISAAC2006 (Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.