ALCOMFT-TR-03-70

MohammadTaghi Hajiaghayi, Naomi Nishimura, Prabhakar Ragde and Dimitrios M. Thilikos
Fast approximation schemes for K_3,3-minor-free or K₅-minor-free graphs
Barcelona. Work packages 2 and 4. October 2003.

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 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₅ or K_3,3 as a minor has local treewidth bounded by 3k+4. As a result, we can design \sl practical polynomial-time approximation schemes for both minimization and maximization problems on these classes of non-planar graphs.

Postscript file: ALCOMFT-TR-03-70.ps.gz (105 kb).