Some new results on the well-quasi-ordering of graphs. (English) Zbl 0556.05058

Orders: description and roles, Proc. Conf. Ordered sets appl., l’Arbresle/France 1982, Ann. Discrete Math. 23, 343-354 (1984).
[For the entire collection see Zbl 0539.00003.]
This paper surveys the methods and results of the first five parts of the authors’ series of papers entitled ”Graph Minors”. (The first and the third of these outstanding papers have already appeared in print, see [J. Comb. Theory, Ser. B 35, 39-61 (1983; Zbl 0521.05062)] and [Graph minors III. Planar tree-width, ibid. 36, 49-64 (1984)].)
From the authors’ abstract: ” We have proved (1) that all graphs G not including a fixed planar graph H as a minor can be constructed by piecing together graphs on a bounded number of vertices in a tree-structure, and (2) by elaborating the Kruskal tree theorem that the class of graphs formed by piecing together graphs of bounded size in tree-structures is well-quasi-ordered. It follows from this that no infinite antichain of finite graphs can include even one planar graph and that there is a ”good” algorithm for testing the presence of a fixed planar graph as a minor.”
Reviewer: T.Andreae


05C99 Graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
05C75 Structural characterization of families of graphs
68Q25 Analysis of algorithms and problem complexity