Graph minors. II. Algorithmic aspects of tree-width. (English) Zbl 0611.05017

[For part I see the authors’ paper in J. Comb. Theory 35, 39-61 (1983; Zbl 0521.05062).]
We introduce an invariant of graphs called the tree-width, and use it to obtain a polynomially bounded algorithm to test if a graph has a subgraph contractible to H, where H is any fixed planar graph. We also nonconstructively prove the existence of a polynomial algorithm to test if a graph has tree-width \(\leq w\), for fixed w. Neither of these is a practical algorithm, as the exponents of the polynomials are large. Both algorithms are derived from a polynomial algorithm for the DISJOINT CONNECTING PATHS problem (with the number of paths fixed), for graphs of bounded tree-width.


05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C38 Paths and cycles
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI