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.