**Reference**:- Erik D. Demaine and MohammadTaghi Hajiaghayi, “Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications”, in
*Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004)*, New Orleans, Louisiana, January 11–13, 2004, pages 833–842. **Abstract**:-
We solve an open problem posed by Eppstein in 1995 [14, 15] and
re-enforced by Grohe [16, 17] concerning locally bounded treewidth in
minor-closed families of graphs. A graph has
*bounded local treewidth*if the subgraph induced by vertices within distance*r*of any vertex has treewidth bounded by a function of*r*(not*n*). Eppstein characterized minor-closed families of graphs with bounded local treewidth as precisely minor-closed families that minor-exclude an apex graph, where an*apex graph*has one vertex whose removal leaves a planar graph. In particular, Eppstein showed that all apex-minor-free graphs have bounded local treewidth, but his bound is doubly exponential in*r*, leaving open whether a tighter bound could be obtained. We improve this doubly exponential bound to a linear bound, which is optimal. In particular, any minor-closed graph family with bounded local treewidth has linear local treewidth. Our bound generalizes previously known linear bounds for special classes of graphs proved by several authors. As a consequence of our result, we obtain substantially faster polynomial-time approximation schemes for a broad class of problems in apex-minor-free graphs, improving the running time from 2^{22O(1/ε)}*n*^{O(1)}to 2^{O(1/ε)}*n*^{O(1)}. **Length**:- The paper is 10 pages.
**Availability**:- The paper is available in PostScript (287k), gzipped PostScript (115k), and PDF (153k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.