##
**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.

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 |