Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 6 (2013) 187–196
The excluded minor structure theorem with
planarly embedded wall
Bojan Mohar ∗
Department of Mathematics, Simon Fraser University, Burnaby, B.C. V5A 1S6, Canada
Received 25 September 2009, accepted 29 May 2012, published online 11 July 2012
Abstract
A graph is “nearly embedded” in a surface if it consists of graph G0 that is embedded
in the surface, together with a bounded number of vortices having no large transactions. It
is shown that every large wall (or grid minor) in a nearly embedded graph, many rows of
which intersect the embedded subgraphG0 of the near-embedding, contains a large subwall
that is planarly embedded within G0. This result provides some hidden details needed for
a strong version of the Robertson and Seymour’s excluded minor theorem as presented
in [1].
Keywords: Graph, graph minor, surface, near-embedding, grid minor, excluded minor.
Math. Subj. Class.: 05C10, 05C82
1 Introduction
A graph is a minor of another graph if the first can be obtained from a subgraph of the
second by contracting edges. One of the highlights of the graph minors theory developed
by Robertson and Seymour is the Excluded Minor Theorem (EMT) that describes a rough
structure of graphs that do not contain a fixed graph H as a minor. Two versions of EMT
appear in [7, 8]; see also [3] and [4].
In [1] and [2] the authors used a strong version of EMT in which it is concluded that
every graph without a fixed minor and whose tree-width is large has a tree-like structure,
whose pieces are subgraphs that are almost embedded in some surface, and in which one of
the pieces contains a large grid minor that is (essentially) embedded in a disk on the surface.
Although not explicitly mentioned, this version of EMT follows from the published results
of Robertson and Seymour [8] by applying standard techniques of routings on surfaces.
∗Supported in part by ARRS, Research Program P1-0297, by an NSERC Discovery Grant and by the Canada
Research Chair program. On leave from Department of Mathematics, University of Ljubljana, Ljubljana, Slove-
nia.
E-mail address: mohar@sfu.ca (Bojan Mohar)
Copyright c© 2013 DMFA Slovenije
188 Ars Math. Contemp. 6 (2013) 187–196
Experts in this area are familiar with these techniques (that are also present in Robertson
and Seymour’s work [6]). However, they may be harder to digest for newcomers in the
area, and thus deserve to be presented in the written form. The purpose of this note is to
provide a proof of an extended version of EMT as stated in [1, Theorem 4.2].
It may be worth mentioning that the proof in [1] does not really need the extended
version of the EMT, but the proof in [2] does. Thus, this note may also be viewed as a
support for the main proof in [2].
We assume that the reader is familiar with the basic notions of graph theory and in
particular with the basic notions related to graph minors; we refer to [3] for all terms and
results not explained here.
2 Walls in near-embeddings
In this section, we present our main lemma, which shows that for every large wall (to be
defined in the sequel) in a “nearly embedded” graph, a large subwall must be contained in
the embedded subgraph of the near-embedding. Let us first introduce the notion of the wall
and some of its elementary properties.
Figure 1: The cylindrical 6-wall Q6
For an integer r ≥ 3, we define a cylindrical r-wall as a graph that is isomorphic to a
subdivision of the graph Qr defined as follows. We start with vertex set V = {(i, j) | 1 ≤
i ≤ r, 1 ≤ j ≤ 2r}, and make two vertices (i, j) and (i′, j′) adjacent if and only if one of
the following possibilities holds:
(1) i′ = i and j′ ∈ {j − 1, j + 1}, where the values j − 1 and j + 1 are considered
modulo 2r.
(2) j′ = j and i′ = i+ (−1)i+j .
Less formally, Qr consists of r disjoint cycles C1, . . . , Cr of length 2r (where V (Ci) =
B. Mohar: The excluded minor structure theorem with planarly embedded wall 189
{(i, j) | 1 ≤ j ≤ 2r}), called the meridian cycles of Qr. Any two consecutive cycles Ci
and Ci+1 are joined by r edges so that the edges joining Ci and Ci−1 interlace on Ci with
those joining Ci and Ci+1 for 1 < i < r. Figure 1 shows the cylindrical 6-wall Q6.
By deleting the edges joining vertices (i, 1) and (i, 2r) for i = 1, . . . , r, we obtain a
subgraph of Qr. Any graph isomorphic to a subdivision of this graph is called an r-wall.
To relate walls and cylindrical walls to (r× r)-grid minors, we state the following easy
correspondence:
(a) Every (4r + 2)-wall contains a cylindrical r-wall as a subgraph.
(b) Every cylindrical r-wall contains an (r × r)-grid as a minor.
(c) Every (r × r)-grid minor contains an b r−12 c-wall as a subgraph.
Lemma 2.1. Suppose that 1 ≤ i < j ≤ r and let t = j − i− 1. Let Si ⊂ Ci and Sj ⊆ Cj
be paths of length at least 2t − 1 in the meridian cycles Ci, Cj of Qr. Then Qr contains t
disjoint paths linking Ci and Cj . Moreover, for each of these paths and for every cycle Ck,
i < k < j, the intersection of the path with Ck is a connected segment of Ck.
Ci
Cj
Si
Sj
Figure 2: Paths linking Si and Sj
Proof. The lemma is easy to prove and the idea is illustrated in Figure 2, in which the
edges on the left are assumed to be identified with the corresponding edges on the right.
The paths are shown by thick lines and the segments Si and Sj are shown by thick broken
lines.
A surface is a compact connected 2-manifold (with or without boundary). The compo-
nents of the boundary are called the cuffs. If a surface S has Euler characteristic c, then the
non-negative number g = 2− c is called the Euler genus of S. Note that a surface of Euler
genus g contains at most g cuffs.
Disjoint cycles C,C ′ in a graph embedded in a surface S are homotopic if there is a
cylinder in S whose boundary components are the cycles C and C ′. The cylinder bounded
by homotopic cycles C,C ′ is denoted by int(C,C ′). Disjoint paths P,Q whose initial
vertices lie in the same cuff C and whose terminal vertices lie in the same cuff C ′ in S
190 Ars Math. Contemp. 6 (2013) 187–196
(possibly C ′ = C) are homotopic if P and Q together with a segment in C and a segment
in C ′ form a contractible closed curve A in S. The disk bounded by A will be denoted
by int(P,Q). The following basic fact about homotopic curves on a surface will be used
throughout (cf., e.g., [5, Propositions 4.2.6 and 4.2.7]).
Lemma 2.2. Let S be a surface of Euler genus g. Then every collection of more than 3g
disjoint non-contractible cycles contains two cycles that are homotopic. Similarly, every
collection of more than 3g disjoint paths, whose ends are on the same (pair of) cuffs in S,
contains two paths that are homotopic.
Let G be a graph and let W = {w0, . . . , wn}, n = |W | − 1, be a linearly ordered
subset of its vertices such that wi precedes wj in the linear order if and only if i < j. The
pair (G,W ) is called a vortex of length n, W is the society of the vortex and all vertices
in W are called society vertices. When an explicit reference to the society is not needed,
we will as well say that G is a vortex. A collection of disjoint paths R1, . . . , Rk in G is
called a transaction of order k in the vortex (G,W ) if there exist i, j (0 ≤ i ≤ j ≤ n)
such that all paths have their initial vertices in {wi, wi+1, . . . , wj} and their endvertices in
W \ {wi, wi+1, . . . , wj}.
Let G be a graph that can be expressed as G = G0 ∪ G1 ∪ · · · ∪ Gv , where G0 is
embedded in a surface S of Euler genus g with v cuffs Ω1, . . . ,Ωv , and Gi (i = 1, . . . , v)
are pairwise disjoint vortices, whose society is equal to their intersection with G0 and is
contained in the cuff Ωi, with the order of the society being inherited from the circular
order around the cuff. Then we say that G is near-embedded in the surface S with vortices
G1, . . . , Gv . A subgraph H of a graph G that is near-embedded in S is said to be planarly
embedded in S if H is contained in the embedded subgraph G0, and there exists a cycle
C ⊆ G0 that is contractible in S and H is contained in the disk on S that is bounded by C.
Our main result is the following.
Theorem 2.3. For every non-negative integers g, v, a there exists a positive integer s =
s(g, v, a) such that the following holds. Suppose that a graph G is near-embedded in the
surface S with vortices G1, . . . , Gv , such that the maximum order of transactions of the
vortices is at most a. Let Q be a cylindrical r-wall contained in G, such that at least
r0 ≥ 3s of its meridian cycles have at least one edge contained in G0. Then Q ∩ G0
contains a cylindrical r′-wall that is planarly embedded in S and has r′ ≥ r0/s.
Proof. Let Cp1 , Cp2 , . . . , Cpr0 (p1 < p2 < · · · < pr0 ) be meridian cycles of Q having an
edge in G0. For i = 1, . . . , r0, let Li be a maximal segment of Cpi containing an edge
in E(Cpi) ∩ E(G0) and such that none of its vertices except possibly the first and the last
vertex are on a cuff. It may be that Li = Cpi if Cpi contains at most one vertex on a
cuff; if not, then Li starts on some cuff and ends on (another or the same) cuff. (We think
of the meridian cycles to have the orientation as given by the meridians in the wall.) At
least r0/(v2 + 1) of the segments Li either start and end up on the same cuffs Ωx and Ωy
(possibly x = y), or are all cycles. In each case, we consider their homotopies. By Lemma
2.2, these segments contain a subset of q ≥ r0/((3g+ 1)(v2 + 1)) homotopic segments (or
cycles). Since we will only be interested in these homotopic segments or cycles, we will
assume henceforth that L1, . . . , Lq are homotopic.
Let us first look at the case when L1, . . . , Lq are cycles. Since s = s(g, v, a) can be
chosen to be arbitrarily large (as long as it only depends on the parameters), we may assume
B. Mohar: The excluded minor structure theorem with planarly embedded wall 191
C C’
C’’
Figure 3: Many contractible cycles
that q is as large as needed in the sequel. If the cycles Li are pairwise homotopic and non-
contractible, then it is easy to see that two of them bound a cylinder in S containing many of
these cycles. This cylinder also contains the paths connecting these cycles; thus it contains
a large planarly embedded wall and hence also a large planarly embedded cylindrical wall.
So, we may assume that the cycles L1, . . . , Lq are contractible. By Lemma 2.1, Q contains
t paths linking any two of these cycles that are t apart in Q, say C = Li and C ′ = Li+t+1.
(Here we take t large enough that the subsequent arguments will work.) Again, many of
these paths either reach C ′ without intersecting any of the cuffs, or many reach the same
cuff Ω. A large subset of them is homotopic. In the former case, the paths linking C ′ with
C ′′ = Li+2t+2 can be chosen so that their initial vertices interlace on C ′ with the end-
vertices of the homotopic paths coming from C. This implies that C or C ′′ lies in the disk
bounded by C ′ (cf. Figure 3). By repeating the argument, we obtain a sequence of nested
cycles and interlaced linkages between them. This clearly gives a large subwall, which
contains a large cylindrical subwall that is planarly embedded. In the latter case, when the
paths from C to C ′ go through the same cuff Ωj , we get a contradiction since the vortex on
Ωj does not admit a transaction of large order, and thus too many homotopic paths cannot
reach C ′′.
x
y
Li
Lj
A
B
C
D
Figure 4: Many homotopic segments joining two cuffs
We get a similar contradiction as in the last case above, when too many homotopic
segments Li start and end up on the same cuffs Ωx and Ωy . We shall give details for the
192 Ars Math. Contemp. 6 (2013) 187–196
case when x 6= y, but the same approach works also if x = y. (In the case when x = y
and the homotopic segments Li are contractible, the proof is similar to the part of the proof
given above.)
Let us consider the “extreme” segments Li, Lj , whose disk int(Li, Lj) contains many
homotopic segments (cf. Figure 4). Let us enumerate these segments as L′1 = Li, L
′
2, . . . ,
L′m = Lj in the order as they appear inside int(Li, Lj). Let C
′
t (for 1 < t < m) be
the meridian cycle containing the segment L′t. Since vortices admit no transactions of
order more than a, at most 4a of the cycles C ′t (1 < t < m) can leave int(Li, Lj). By
adjustingm, we may thus assume that none of them does. In particular, each L′t has another
homotopic segment in int(Li, Lj). Since there are no transactions of order more than a,
there is a large subset of the cycles C ′t that follow each other in int(Li, Lj) as shown by
the thick cycles in Figure 4. Consider four of these meridian cycles A,B,C,D that are
pairwise far apart in the wall Q and appear in the order A,B,C,D within int(Li, Lj).
Then A and C are linked in Q by a large collection of disjoint paths by Lemma 2.1. At
most 8a of these paths can escape intersecting two fixed segments L′u and L
′
v of B or two
such segments of D by passing through a vortex. All other paths linking A and C intersect
either two segments of B or two segments of D. However, this is a contradiction since the
paths linking A and C can be chosen in Q so that each of them intersects each meridian
cycle in a connected segment (Lemma 2.1). This completes the proof.
3 The excluded minor structure
In this section, we define some of the structures found in Robertson-Seymour’s Excluded
Minor Theorem [7] which describes the structure of graphs that do no contain a given
graph as a minor. Robertson and Seymour proved a strengthened version of that theorem
that gives a more elaborate description of the structure in [8]. Our terminology follows that
introduced in [1].
Let G0 be a graph. Suppose that (G′1, G
′
2) is a separation of G0 of order t ≤ 3, i.e.,
G0 = G
′
1∪G′2, whereG′1∩G′2 = {v1, . . . , vt} ⊂ V (G0), 1 ≤ t ≤ 3, V (G′2)\V (G′1) 6= ∅.
Let us replace G0 by the graph G′, which is obtained from G′1 by adding all edges vivj
(1 ≤ i < j ≤ t) if they are not already contained in G′1. We say that G′ has been obtained
from G0 by an elementary reduction. If t = 3, then the 3-cycle T = v1v2v3 in G′ is called
the reduction triangle. Every graph G′′ that can be obtained from G0 by a sequence of
elementary reductions is a reduction of G0.
We say that a graph G0 can be embedded in a surface Σ up to 3-separations if there is a
reduction G′′ of G0 such that G′′ has an embedding in Σ in which every reduction triangle
bounds a face of length 3 in Σ.
Let H be an r-wall in the graph G0 and let G′′ be a reduction of G0. We say that the
reductionG′′ preservesH if for every elementary reduction used in obtainingG′′ fromG0,
at most one vertex of degree 3 in H is deleted. (With the above notation, G′2 \G′1 contains
at most one vertex of degree 3 in H .)
Lemma 3.1. Suppose that G′′ is a reduction of the graph G0 and that G′′ preserves an
r-wall H in G0. Then G′′ contains an b(r + 1)/3c-wall, all of whose edges are contained
in the union of H and all edges added to G′′ when performing elementary reductions.
Proof. Let H ′ be the subgraph of the r-wall H obtained by taking every third row and
every third “column”. See Figure 5 in which H ′ is drawn with thick edges. It is easy to
B. Mohar: The excluded minor structure theorem with planarly embedded wall 193
Figure 5: Smaller wall contained in a bigger wall
see that for every elementary reduction we can keep a subgraph homeomorphic to H ′ by
replacing the edges of H ′ which may have been deleted by adding some of the edges vivj
involved in the reduction. The only problem would occur when we lose a vertex of degree
3 and when all vertices v1, v2, v3 involved in the elementary reduction would be of degree
3 in H ′. However, this is not possible since G′′ preserves H .
Suppose that for i = 0, . . . , n, there exist vertex sets, called parts, Xi ⊆ V (G), with
the following properties:
(V1) Xi ∩W = {wi, wi+1} for i = 0, . . . , n, where wn+1 = wn,
(V2)
⋃
0≤i≤nXi = V (G),
(V3) every edge of G has both endvertices in some Xi, and
(V4) if i ≤ j ≤ k, then Xi ∩Xk ⊆ Xj .
Then the family (Xi ; i = 0, . . . , n) is called a vortex decomposition of the vortex (G,W ).
For i = 1, . . . , n, denote by Zi = (Xi−1 ∩Xi) \W . The adhesion of the vortex decom-
position is the maximum of |Zi|, for i = 1, . . . , n. The vortex decomposition is linked if
for i = 1, . . . , n − 1, the subgraph of G induced on the vertex set Xi \W contains a col-
lection of disjoint paths linking Zi with Zi+1. Clearly, in that case |Zi| = |Zi+1|, and the
paths corresponding to Zi ∩ Zi+1 are trivial. Note that (V1) and (V3) imply that there are
no edges between nonconsecutive society vertices of the vortex. Let us remark that every
vortex (G,W ), in which wi, wj are non-adjacent for |i − j| ≥ 2, admits a linked vortex
decomposition; just take Xi = (V (G) \W ) ∪ {wi, wi+1}.
The (linked) adhesion of the vortex is the minimum adhesion taken over all (linked)
decompositions of the vortex. Let us observe that in a linked decomposition of adhesion q,
there are q disjoint paths linking Z1 with Zn in G−W . For us it is important to note that
a vortex with adhesion less than k does not admit a transaction of order more than k.
Let G be a graph, H an r-wall in G, Σ a surface, and α ≥ 0 an integer. We say that
G can be α-nearly embedded in Σ if there is a set of at most α cuffs C1, . . . , Cb (b ≤ α)
in Σ, and there is a set A of at most α vertices of G such that G − A can be written
194 Ars Math. Contemp. 6 (2013) 187–196
as G0 ∪ G1 ∪ · · · ∪ Gb where G0, G1, . . . , Gb are edge-disjoint subgraphs of G and the
following conditions hold:
(N1) G0 can be embedded in Σ up to 3-separations with G′′ being the corresponding
reduction of G0.
(N2) If 1 ≤ i < j ≤ b, then V (Gi) ∩ V (Gj) = ∅.
(N3) Wi = V (G0) ∩ V (Gi) = V (G′′) ∩ Ci for every i = 1, . . . , b.
(N4) For every i = 1, . . . , b, the pair (Gi,Wi) is a vortex of adhesion less than α, where
the ordering of Wi is consistent with the (cyclic) order of these vertices on Ci.
The vertices in A are called the apex vertices of the α-near embedding. The subgraph
G0 ofG is said to be the embedded subgraph with respect to the α-near embedding and the
decomposition G0, G1, . . . , Gb. The pairs (Gi,Wi), i = 1, . . . , b, are the vortices of the α-
near embedding. The vortex (Gi,Wi) is said to be attached to the cuff Ci of Σ containing
Wi.
If G is α-near-embedded in S, let G0, G1, . . . , Gb be as above and let G′′ be the re-
duction of G0 that is embedded in S. If H is an r-wall in G, we say that H is captured in
the embedded subgraph G0 of the α-near-embedding if H is preserved in the reduction G′′
and for every separation G = K ∪ L of order less than r, where G0 ⊆ K, at least 23 of the
degree-3 vertices of H lie in K.
We shall use the following theorem which is a simplified version of one of the corner-
stones of Robertson and Seymour’s theory of graph minors, the Excluded Minor Theorem,
as stated in [8]. For a detailed explanation of how the version in this paper can be derived
from the version in [8], see the appendix of [1].
Theorem 3.2 (Excluded Minor Theorem). For every graph R, there is a constant α such
that for every positive integer w, there exists a positive integer r = r(R,α,w), which tends
to infinity with w for any fixed R and α, such that every graph G that does not contain an
R-minor either has tree-width at most w or contains an r-wall H such that G has an α-near
embedding in some surface Σ in which R cannot be embedded, and H is captured in the
embedded subgraph of the near-embedding.
We can add the following assumptions about the r-wall in Theorem 3.2.
Theorem 3.3. It may be assumed that the r-wall H in Theorem 3.2 has the following
properties:
(a) H is contained in the reduction G′′ of the embedded subgraph G0.
(b) H is planarly embedded in Σ, i.e., every cycle in H is contractible in Σ and the outer
cycle of H bounds a disk in Σ that contains H .
(c) We may prespecify any constant ρ and ask that the face-width of G′′ be at least ρ.
(d) G′′ is 3-connected.
Proof. The starting point is Theorem 3.2. By making additional elementary reductions if
necessary, we can achieve (d). The property (c) is attained as follows. If the face-width is
too small, then there is a set of less than ρ vertices whose removal reduces the genus of the
embedding of G′′. We can add these vertices in the apex set and repeat the procedure as
B. Mohar: The excluded minor structure theorem with planarly embedded wall 195
long as the face-width is still smaller than ρ. The only subtlety here is that the constant α
in Theorem 3.2 now depends not only on R but also on ρ. See also [4].
After removing the apex set A, we are left with an (r−α)-wall in G−A. By applying
Lemma 3.1, we may assume that H is contained in the reduced graph G′′ ∪G1 ∪ · · · ∪Gb.
The wall H contains a large cylindrical wall Q. Since the vortices have bounded adhesion,
they do not have large transactions. Since the wall is captured in G′′, edges of many
meridians of Q lie in G′′. Therefore, we can apply Theorem 2.3 for the near embedding of
the reduced graph together with the vortices. This shows that a large cylindrical subwall
of Q is planarly embedded in the surface. The size r′ of this smaller wall still satisfies the
condition that r′ = r′(R,α,w)→∞ as w increases.
It is worth mentioning that there are other ways to show that a graph with large enough
tree-width that does not contain a fixed graph R as a minor contains a subgraph that is
α-near-embedded in some surface Σ in which R cannot be embedded, and moreover, there
is an r-wall planarly embedded in Σ (after reductions taking care of at most 3-separations).
Let us describe two of them:
(A) Large face-width argument: One can use property (c) in Theorem 3.3 that the face-
width ρ can be made as large as we want if α = α(R,w, ρ) is large enough. Once
we have that, it follows from [6] that there is a planarly embedded r-wall, where
r = r(R, ρ) → ∞ as ρ → ∞. While this easy argument is sufficient for most
applications, it appears to be slightly weaker than Theorem 3.3 since the quantifiers
change. The difference is that the number of apex vertices is no longer bounded as
a function of α = α(R) but rather as a function depending on R and r, where the
upper bound has linear dependence on r, i.e. it is of the form β(R)r. However, other
parameters of the near-embedding keep being only dependent on R.
(B) Irrelevant vertex: The third way of establishing the same result is to go through
the proof of Robertson and Seymour that there is an irrelevant vertex, i.e. a vertex
v such that G has an R-minor if and only if G − v has. (Compared to the later,
more abstract parts of the graph minors series of papers, this part is very clean and
well understood; it could (and should) be explained in a(ny) serious graduate course
on graph minors.) In that proof, one starts with an arbitrary wall W that is large
enough. A large wall exists since the tree-width is large. Then one compares the
W -bridges attached to W . They may give rise to ≤ 3-separations, to jumps (paths
in bridges whose addition to W yields a nonplanar graph), crosses (pairs of disjoint
paths attached to the same planar face of W whose addition to W yields a nonplanar
graph). If there are many disjoint jumps or crosses on distinct faces of W , one can
find an R-minor. If there are just a few, there is a large planar wall. If there are many
of them on the same face, we get a structure of a vortex with bounded transactions
(or else an R-minor can be discovered). The proof then discusses ways for many
jumps and crosses but no large subset of them being disjoint. One way is to have a
small set of vertices whose removal destroys most of these jumps and crosses. This
gives rise to the apex vertices. The final conclusion is that the jumps and crosses can
affect only a bounded part of the wall, so after the removal of the apex vertices and
after elementary reductions which eliminate≤ 3-separations, there is a large subwall
W0 such that no jumps or crosses are involved in it. The “middle” vertex in W0 is
then shown to be irrelevant.
196 Ars Math. Contemp. 6 (2013) 187–196
For our reference, only this planar wall is needed. By being planar, we mean that
the rest of the graph is attached only to the outer face of this wall. Then we define
the tangle corresponding to this wall and the proof of the EMT preserves this tangle
while making the modifications yielding to an α-near-embedding.
References
[1] T. Böhme, K. Kawarabayashi, J. Maharry and B. Mohar, Linear connectivity forces large com-
plete bipartite minors, J. Combin. Theory, Ser. B 99 (2009), 557–582.
[2] T. Böhme, K. Kawarabayashi, J. Maharry and B. Mohar, K3,k-minors in large 7-connected
graphs, submitted to J. Combin. Theory, Ser. B, May 2008.
[3] R. Diestel, Graph Theory, 3rd Edition, Springer, 2005.
[4] K. Kawarabayashi and B. Mohar, Some recent progress and applications in graph minor theory,
Graphs Combin. 23 (2007), 1–46.
[5] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore,
MD, 2001.
[6] N. Robertson and P. D. Seymour, Graph minors. VII. Disjoint paths on a surface, J. Combin.
Theory Ser. B 45 (1988), 212–254.
[7] N. Robertson and P. D. Seymour, Graph minors. XVI. Excuding a non-planar graph, J. Combin.
Theory Ser. B 89 (2003), 43–76.
[8] N. Robertson and P. D. Seymour, Graph minors. XVII. Taming a vortex, J. Combin. Theory
Ser. B 77 (1999), 162–210.