**Reference**:- Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos, “Bidimensional Parameters and Local Treewidth”,
*SIAM Journal on Discrete Mathematics*, volume 18, number 3, 2004, pages 501–511. **Abstract**:-
For several graph-theoretic parameters such as vertex
cover and dominating set, it is known that if their sizes 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 graph parameters including all those for which such 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 an increasing function*t*such that every graph*G*∈*F*has treewidth at most*t*(*P*(*G*)). We prove as our main result that, for a large family of graph parameters called*contraction-bidimensional*, 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 graph parameters, and thus this result is in some sense tight. In addition we show that, for a slightly smaller family of graph parameters called*minor-bidimensional*, all minor-closed graph families*F*excluding some fixed graphs have the parameter-treewidth property. The contraction-bidimensional parameters include many domination and covering graph parameters such as vertex cover, feedback vertex set, dominating set, edge-dominating set,*q*-dominating set (for fixed*q*). We use our theorems to develop new fixed-parameter algorithms in these contexts. **Comments**:- This paper is also available from SIAM.
**Availability**:- The paper is available in PostScript (408k), gzipped PostScript (180k), and PDF (174k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- Bidimensional_LATIN2004 (Bidimensional Parameters and Local Treewidth)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.