Graph minors. V. Excluding a planar graph

摘要: Abstract We prove that for every planar graph H there is a number w such with no minor isomorphic to can be constructed from graphs at most vertices, by piecing them together in tree structure. This has several consequences; example, it implies that: (i) if A set of member another, and some planar, then finite; (ii) fixed polynomial time algorithm test an arbitrary H; (iii) generalization theorem Erdos Posa (concerning the maximum disjoint circuits graph) structures other than circuits.