×

zbMATH — the first resource for mathematics

Graph minors. XVI: Excluding a non-planar graph. (English) Zbl 1023.05040
Summary: This paper contains the cornerstone theorem of the series. We study the structure of graphs with no minor isomorphic to a fixed graph \(L\), when \(L\) is non-planar. (The case when \(L\) is planar was studied in an earlier paper.) We find that every graph with no minor isomorphic to \(L\) may be constructed by piecing together in a tree-structure graphs each of which “almost” embeds in some surface in which \(L\) cannot be embedded.

MSC:
05C10 Planar graphs; geometric and topological aspects of graph theory
05C83 Graph minors
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dirac, G, A property of 4-chromatic graphs and remarks on critical graphs, J. London math. soc., 27, 85-92, (1952) · Zbl 0046.41001
[2] Duffin, R.J, Topology of series-parallel networks, J. math. anal. appl., 10, 303-318, (1965) · Zbl 0128.37002
[3] Erdös, P; Szekeres, G, A combinatorial problem in geometry, Composito. math., 2, 463-470, (1935) · Zbl 0012.27010
[4] Robertson, N; Seymour, P.D, Graph minors. V. excluding a planar graph, J. combin. theory ser. B, 41, 92-114, (1986) · Zbl 0598.05055
[5] Robertson, N; Seymour, P.D, Graph minors. IX. disjoint crossed paths, J. combin. theory ser. B, 49, 40-77, (1990) · Zbl 0741.05044
[6] Robertson, N; Seymour, P.D, Graph minors. X. obstructions to tree-decomposition, J. combin. theory ser. B, 52, 153-190, (1991) · Zbl 0764.05069
[7] Robertson, N; Seymour, P.D, Graph minors. XII. distance on a surface, J. combin. theory ser. B, 64, 240-272, (1995) · Zbl 0840.05016
[8] Robertson, N; Seymour, P.D, Graph minors. XIV. extending an embedding, J. combin. theory ser. B, 65, 23-50, (1995) · Zbl 0840.05017
[9] Robertson, N; Seymour, P.D, Graph minors. XV. giant steps, J. combin. theory ser. B, 68, 112-148, (1996) · Zbl 0860.05023
[10] Robertson, N; Seymour, P.D; Thomas, R, Quickly excluding a planar graph, J. combin. theory ser. B, 62, 323-348, (1994) · Zbl 0807.05023
[11] Seese, D.G; Wessel, W, Grids and their minors, J. combin. theory ser. B, 47, 349-360, (1989) · Zbl 0636.05023
[12] Wagner, K.A, Über eine eigenshaft der ebenen komplexe, Math. ann., 114, 570-590, (1937) · JFM 63.0550.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.