**Reference**:- Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Bidimensional Parameters and Local Treewidth”, in
*Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN 2004)*, Lecture Notes in Computer Science, volume 2976, Buenos Aires, Argentina, April 5–8, 2004, pages 109–118. **Abstract**:-
For several graph theoretic parameters such as vertex cover and dominating set,
it is known that if their values are bounded by
*k*then the treewidth of the graph is bounded by some function of*k*. This fact is used as the main tool for the design of several fixed-parameter algorithms on minor-closed graph classes such as planar graphs, single-crossing-minor-free graphs, and graphs of bounded genus. In this paper we examine the question whether similar bounds can be obtained for larger minor-closed graph classes, and for general families of parameters including all the parameters where such a behavior has been reported so far.Given a graph parameter

*P*, we say that a graph family*F*has the*parameter-treewidth property for P*if there is a function*f*(*p*) such that every graph*G*in*F*with parameter at most*p*has treewidth at most*f*(*p*). We prove as our main result that, for a large family of parameters called*contraction-bidimensional parameters*, a minor-closed graph family*F*has the parameter-treewidth property if*F*has bounded local treewidth. We also show “if and only if” for some parameters, and thus this result is in some sense tight. In addition we show that, for a slightly smaller family of parameters called*minor-bidimensional parameters*, all minor-closed graph families*F*excluding some fixed graphs have the parameter-treewidth property. The bidimensional parameters include many domination and covering parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set,*q*-dominating set (for fixed*q*). We use these theorems to develop new fixed-parameter algorithms in these contexts. **Comments**:- This paper is also available from SpringerLink.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (180k), gzipped PostScript (72k), and PDF (224k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Bidimensional_SIDMA (Bidimensional Parameters and Local Treewidth)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.