Mathematical Reviews 2001c:05132

Diameter and treewidth in minor-closed graph families
David Eppstein
Algorithmica 27:275–291, 2000
Mathematical Reviews 2001c:05132, 2001
Reviewed by Xiao Tie Deng

The main result of this paper is that any minor-closed family has the diameter-tree width property if and only if it does not contain all apex graphs (graphs that become planar if a vertex, the apex, is removed). This property guarantees that every graph in the family with diameter no more than $D$ has treewidth no more than $f(D)$, where $f$ is a fixed function. Consequently, linear time approximation schemes for several optimization problems on these graphs are obtained, as are linear time algorithms for subgraph isomorphism and induced subgraph isomorphism.

Fano Experimental Web Server, D. Eppstein, School of Information & Computer Science, UC Irvine
Made on a Mac Valid XHTML 1.0!