Robertson, Neil; Seymour, P. D. Graph minors. II. Algorithmic aspects of tree-width. (English) Zbl 0611.05017 J. Algorithms 7, 309-322 (1986). [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. Cited in 15 ReviewsCited in 485 Documents 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 Keywords:contractability; tree-width; polynomially bounded algorithm; planar graph; polynomial algorithm Citations:Zbl 0598.05055; Zbl 0598.05042; Zbl 0548.05025; Zbl 0568.05025; Zbl 0521.05062 PDFBibTeX XMLCite \textit{N. Robertson} and \textit{P. D. Seymour}, J. Algorithms 7, 309--322 (1986; Zbl 0611.05017) Full Text: DOI