Graph minors. V. Excluding a planar graph. (English) Zbl 0598.05055

Robertson, Neil; Seymour, P. D.

J. Comb. Theory, Ser. B 41, 92-114 (1986).

[For part I see the authors’ paper ibid. 35, 39-61 (1983; Zbl 0521.05062), for part III see their paper ibid. 36, 49-64 (1984; Zbl 0548.05025), for part VI see ibid., 115-138 (1986; Zbl 0598.05042). See also their survey paper in Surveys in Combinatorics 1985, Pap. 10th Br. Combin. Conf., Glasgow/Scotl. 1985, Lond. Math. Soc. Lect. Note Ser. 103, 153-171 (1985; Zbl 0568.05025).]
Minors of graphs are obtained by contraction of subgraphs. A decomposition of a graph is a covering of both the vertices and edges by subgraphs, considered as a graph by connecting any two meeting pieces.
It is shown that for each planar graph H there exists a number w such that any graph with no minor isomorphic to H admits a tree-decomposition with pieces of cardinality at most w. In fact this is proven first for H being a finite dimensional grid. As any planar graph is the minor of some such grid, the final result is obtained.
Some consequences are as follows: There is no infinite family of graphs containing a planar one, and in which no graph is isomorphic to a minor of another one. Deciding whether a graph admits a fixed planar graph as a minor, is polynomially solvable. There is a characterization of planar graphs as those graphs which satisfy a property analogous to the one shown by Erdős and Posa for circuits.

Reviewer: F.Plastria

MSC:

05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05	Trees

Keywords:

graph minors; tree-width; Minors of graphs; contraction of subgraphs; planar graphs

Citations:

Zbl 0521.05062; Zbl 0548.05025; Zbl 0598.05042; Zbl 0568.05025

References:

[1]	Bergmann, H, Ein planaritätskriterium für endliche graphen, Elem. math., 37, 49-51, (1982) · Zbl 0484.05032
[2]	Buneman, P, A characterization of rigid circuit graphs, Discrete math., 9, 205-212, (1974) · Zbl 0288.05128
[3]	Dirac, G.A, On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[4]	Erdös, P; Pósa, L, On independent circuits contained in a graph, Canad. J. math., 17, 347-352, (1965) · Zbl 0129.39904
[5]	Gavril, F, The intersection graphs of subtrees in trees are exactly the chordal graphs, J. combin. theory ser. B, 16, 47-56, (1974) · Zbl 0266.05101
[6]	Gyárfás, A; Lehel, J, A Helly-type problem in trees, (), 571-584
[7]	Györi, E, On the division of graphs to connected subgraphs, Combinatorics, colloq. math. soc. János bolyai, 18, 485-494, (1978) · Zbl 0388.05008
[8]	Lovász, L, A homology theory for spanning trees of a graph, Acta math. acad. sci. hungar., 30, 241-251, (1977) · Zbl 0403.05040
[9]	Robertson, Neil; Seymour, P.D, Graph minors. I. excluding a forest, J. combin. theory ser. B, 35, 39-61, (1983) · Zbl 0521.05062
[10]	{\scNeil Robertson and P. D. Seymour}, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, in press. · Zbl 0611.05017
[11]	{\scNeil Robertson and P. D. Seymour}, Graph minors. IV. Tree-width and well-quasiordering, submitted for publication.
[12]	{\scNeil Robertson and P. D. Seymour}, Graph minors. VII. Disjoint paths on a surface, submitted for publication. · Zbl 0658.05044
[13]	Tutte, W.T, From matrices to graphs, Canad. J. math., 16, 108-127, (1964) · Zbl 0138.19202