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.

MSC:

 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: