Abstract:
|
As the class of graphs of bounded treewidth is of limited size,
we need to solve NP-hard problems for wider classes of graphs than this
class. Eppstein introduced a new concept which can be considered as a
generalization of bounded treewidth. A graph G has {em locally bounded
treewidth} if for each vertex v of G, the treewidth of the subgraph of G
induced on all vertices of distance at most r from v is only a function of
r, called local treewidth. So far the only graphs determined to have small
local treewidth are planar graphs. In this paper, we prove that any graph
excluding one of K_{5} or K_{3,3} as a minor has local treewidth bounded by
3k+4. As a result, we can design practical polynomial-time approximation
schemes for both minimization and maximization problems on these classes of
non-planar graphs. |