Graph minors. III. Planar tree-width (Q799684): Difference between revisions

[For part I see ibid. 35, 39-61 (1983; Zbl 0521.05062.] This paper continues the important work by the authors on graph minors. A graph H is a minor of a graph G if H can be obtained from a subgraph of G by contraction. The tree decomposition of a graph G is a pair (T,X) where T is a tree and X is a family of subsets of V(G): \(X=\{X_ t:\quad t\in V(T)\}\) such that (i) the union of the \(X_ t\) is V(G); (ii) for every edge e of G, there exists an \(X_ t\) containing both ends of e; and (iii) for t, t', t''\(\in V(T)\), if t' is on the path of T between t and t'', then \(X_ t\cap X_{t''}\subseteq X_{t'}.\) The width of the tree decomposition is the maximum of \(| X_ t| -1.\) The graph G has tree-width w if w is the minimum width of any tree decomposition of G. The author's main result is: For every planar graph H, there is a number w such that every planar graph with no minor isomorphic to H has tree- width \(\leq w\).