| Publication Title: |
Equivalence of Local Treewidth and Linear Local Treewidth and its Algorithmic Applications |
| Publication Author: |
Demaine, Erik |
| Additional Authors: |
Mohammad Taghi Hagiaghagi |
| LCS Document Number: |
MIT-LCS-TR-903 |
| Publication Date: |
5-29-2003 |
| LCS Group: |
Theory of Computation |
| Additional URL: |
|
| Abstract: |
| We solve an open problem posed by Eppstein in 1995 and re-enforced by Grohe
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^(2^(2^O(1/epsilon))) n^O(1) to 2^O(1/epsilon) n^O(1). |
| To obtain this publication: |
|
|
|
To purchase a printed copy of this publication please contact
MIT
Document Services.
|