**Reference**:- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction”, in
*Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006)*, Lecture Notes in Computer Science, volume 4288, Calcutta, India, December 18–20, 2006, pages 3–15. **Abstract**:-
We explore the three main avenues of research still unsolved in the
algorithmic graph-minor theory literature, 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. 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 (379k), gzipped PostScript (160k), and PDF (221k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GridWagner_Algorithmica (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.