Low Polynomial Exclusion∗

of Planar Graph Patterns

Jean-Florent Raymond1,2,3 and Dimitrios M. Thilikos1,4

1 LABORATOIRE D’INFORMATIQUE, DE ROBOTIQUE ET DE MICROÉLECTRONIQUE (LIRMM)
MONTPELLIER, FRANCE
E-mail: jean-florent.raymond@mimuw.edu.pl; sedthilk@thilikos.info

2 FACULTY OF MATHEMATICS, INFORMATICS AND MECHANICS

UNIVERSITY OF WARSAW
WARSAW, POLAND

3 UNIVERSITY OF MONTPELLIER
FRANCE

4 DEPARTMENT
OF MATHEMATICS
NATIONAL AND KAPODISTRIAN UNIVERSITY OF ATHENS
ATHENS, GREECE

Received May 30, 2013; Revised October 24, 2015

Published online 2 December 2015 in Wiley Online Library (wileyonlinelibrary.com).

DOI 10.1002/jgt.22009

Abstract: The celebrated grid exclusion theorem states that for every
h-vertex planar graph H, there is a constant ch such that if a graph G does
not contain H as a minor then G has treewidth at most ch . We are looking
for patterns of H where this bound can become a low degree polynomial.
We provide such bounds for the following parameterized graphs: the wheel
(ch = O(h)), the double wheel (ch = O(h2 · log2 h)), any graph of pathwidth

∗
Contract grant sponsor: The second author has been co-financed by the E.U.
(European Social Fund—ESF) and Greek national funds through the Operational
Program “Education and Lifelong Learning” of the National Strategic Reference
Framework (NSRF) Research Funding Program: “Thales. Investing in knowledge
society through the European Social Fund.”
Journal of Graph Theory

C 2015 Wiley Periodicals, Inc.

26
 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 27

at most 2 (ch = O(h2 )), and the yurt graph (ch = O(h4 )). C 2015 Wiley Periodicals,
Inc. J. Graph Theory 84: 26–44, 2017

Keywords: treewidth; graph minors

1. INTRODUCTION

Treewidth is one of the most important graph invariants in modern graph theory. It has
been introduced in [21] by Robertson and Seymour as one of the cornerstones of their
Graph Minors series. Apart from its huge combinatorial value, it has been extensively
used in graph algorithm design (see [6] for an extensive survey on treewidth). On an
intuitive level, treewidth expresses how close the topology of the graph is to that of a tree
and, in a sense, can be seen as a measure of the “global connectivity” of a graph.
Formally, a tree decomposition of a graph G is a pair (T, X ) where T is a tree and X
a family (Xt )t∈V (T ) of subsets of V (G) (called bags) indexed by elements of V (T ) and
such that

(i) t∈V (T ) Xt = V (G);
(ii) for every edge e of G there is an element of X containing both ends of e;
(iii) for every v ∈ V (G), the subgraph of T induced by {t ∈ V (T ) | v ∈ Xt } is connected.
The width of a tree decomposition is equal to maxt∈V (T ) |Xt | − 1, while the treewidth
of G, written tw(G), is the minimum width of any of its tree decompositions. Similarly
one may define the notions of path decomposition and pathwidth by additionally asking
that T is a path (see Section 2).
We say that a graph H is a minor of a graph G if a graph isomorphic to H can be
obtained from a subgraph of G by applying a series of edge contractions, and we denote
this fact by H m G.

The grid exclusion theorem. One of the most celebrated results from the Graph Minors
series of Robertson and Seymour is the following result, also known as the grid exclusion
theorem.
Proposition 1.1. ([22]). There exists a function f : N → N such that, for every for every
planar graph H on h vertices, every graph G that does not contain a minor isomorphic
to H has treewidth at most f (h).
The original proof the the above result in [22] did not provided any explicit esti-
mation for the function f . Later, in [23], Robertson, Seymour, and Thomas proved the
same result for f (h) = 2O(h ) , while a less complicated proof appeared in [12]. The
5

bound f (h)  h − 2 was also obtained in [2] in the case where H is required to be a
forest.
For a long time, whether Proposition 1.1. can be proved for a polynomial f was an
open problem. In [23], an (h2 · log h) lower bound was provided for the best possible
estimation of f and was also conjectured that the optimal estimation should not be far
away from this lower bound. In fact, a more precise variant of the same conjecture was
given by Demaine, Hajiaghayi, and Kawarabayashi in [11] where they conjectured that
Proposition 1.1. holds for f (h) = O(h3 ). The bounds of [23] were recently improved
by Kawarabayashi and Kobayashi [16], where they show that Proposition 1.1. holds

Journal of Graph Theory DOI 10.1002/jgt

28 JOURNAL OF GRAPH THEORY

for f (h) = 2O(h·log h) . The same bounds were obtained by Leaf and Seymour [18]. Until
recently, this was the best known estimation of the function f .
Very recently, in a breakthrough result [9], Chekuri and Chuzhoy proved that Proposi-
tion 1.1. holds for f (h) = O(h228 ). The remaining open question is whether the degree
of this polynomial bound can be substantially reduced in general. In this direction, one
may still consider restrictions either on the graph G or on the graph H that yield a low
polynomial dependence between the treewidth and the size of the excluded minor. In the
first direction, Demaine and Hajiaghayi proved in [10] that, when G is restricted to be-
long in some graph class excluding some fixed graph R as a minor, then Proposition 1.1.
(optimally) holds for f (h) = O(h). Similar results have been proved by Fomin, Saurabh,
and Lokshtanov, in [15], for the case where G is either a unit disk graph or a map graph
that does not contain a clique as a subgraph.
In a second direction, one may consider H to be some specific planar graph and find
a good upper bound for the treewidth of the graphs that exclude it as a minor. More
generally, we can consider a parametrized class of planar graphs Hk where each graph
in Hk has size bounded by a polynomial in k, and prove that the following fragment of
Proposition 1.1. holds for some low degree polynomial function f : N → N:
∀k  0 ∀H ∈ Hk , i f H m G then tw(G)  f (k). (1)
The question can be stated as follows: find pairs (Hk , g(k)) for which (1) holds for
some f (k) = O(g(k), where Hk is as general as possible and g is as small as possible (and
certainly polynomial). It is known, for example, that (1) holds for the pair ({Ck }, k), where
Ck is the cycle or a path of k vertices (see e.g. [5, 14]), and for the pair ({K2,k }, k), (see [8]).
Two more results in the same direction that appeared recently are the following: according
to the result of Birmel, Bondy, and Reed in [4], (1) holds for the pair (Pk , k2 ) where Pk
contains all minors of K2 × Ck (we denote by K2 × Ck the Cartesian product of K2 and
the cycle of k vertices, also known as the k-prism). Finally, one of the consequences of
the recent results of Leaf and Seymour in [18], implies that (1) holds for the pair (Fr , k),
where Fr contains every graph on r vertices that contains a vertex that meets all its cycles.

Our results. In this article we provide polynomially bounded minor exclusion theorems
for the following parameterized graph classes:
Hk0 : containing all graphs on k vertices that have pathwidth at most 2.
Hk1 : containing all minors of a wheel on k + 1 vertices – see Figure 1.
Hk2 : containing all minors of a double wheel on k + 2 vertices – see Figure 1.
Hk3 : containing all minors of the yurt graph on 2k + 1 vertices (i.e. the graph obtained
it we take a (2 × k)-grid and add a new vertex adjacent with all the vertices of its
“upper layer” – see Fig. 4).
Notice that none of the above classes is minor comparable with the classes Pk and Fk
treated in [4] and [18]. Moreover, Hk1 ⊂ Hk2 ⊂ Hk3 , while Hk0 is not minor comparable
with the other three. In this article we prove that (1) holds for the pairs:
r (H0 , k2 ),
k
r (H1 , k),
k

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 29

r (H2 , k2 log2 n), and

k
r (H3 , k4 ).
k

The above results are presented in detail, without the O-notation, in Section 3. All of
our proofs use as a departure point the results of Leaf and Seymour in [18].

2. DEFINITIONS

All graphs in this article are finite and simple, i.e., do not have loops nor multiple edges.
We denote by V (G) (resp. E(G)) the sets of vertices (resp. edges) of G. For every i, j ∈ N,
i  j, the notation [[i, j]] stands for the interval of integers {i, i + 1, . . . , j}. Logarithms
are binary.
Definition 2.1. (path decomposition, pathwidth). A path decomposition of a graph G
is a tree decomposition T of G such that T is a path. Its width is the width of the tree
decomposition T and the pathwidth of G, written pw(G), is the minimum width of any
of its path decompositions. An optimal path decomposition is a path decomposition of
minimum width.
Definition 2.2 (contraction and dissolution). The contraction of an edge {u, v} in a
graph G is the operation which creates a new vertex adjacent to the neighbors of u and
those of v, and deletes both u and v. The dissolution of a vertex of degree two is the
contraction of one of the edges incident with it.
Definition 2.3 (minor model). A minor model (sometimes abbreviated model) of a
graph H in a graph G is a pair (M, ϕ) where M is a set of pairwise disjoint subsets
of V (G) such that ∀X ∈ M, G[X] is connected and ϕ : V (H ) → M is a bijection that
satisfies ∀{u, v} ∈ E(H ), ∃u
∈ ϕ(u), ∃v
∈ ϕ(v), {u
, v
} ∈ E(G). We say that a graph
H is a minor of a graph G (H m G) if there is a minor model of H in G. Notice that H
is a minor of G if H can be obtained from subgraph of G by edges contractions.
Definition 2.4 (linked set). Let G be a graph and S ⊆ V (G). The set S is said to be linked
in G if for every two subsets X1 , X2 of S (not necessarily disjoint) such that |X1 | = |X2 |,
there is a set Q of |X1 | (vertex-)disjoint paths between X1 and X2 in G whose length is not
one (but can be null) and whose endpoints only are in S.
Definition 2.5 (separation). A pair (A, B) of subsets of V (G) is a called a separation
of order k in G if k = |A ∩ B|, none of A, B is a subset of the other, and there is no edge
of G between A \ B and B \ A.
Definition 2.6 (left-contains, [18]). Let H be a graph on r vertices, G a graph and
(A, B) a separation of order r in G. We say that (A, B)left-contains H if G[A] contains a
minor model M of H such that ∀M ∈ M, |M ∩ (A ∩ B)| = 1
Definition 2.7 (Trees and cycles). Given a tree T we denote by L(T ) the set of its
leaves, i.e. vertices of degree 1 and by diam(T ) its diameter, that is the maximum length
(in number of edges) of a path in T.
For every two vertices u, v ∈ V (T ), there is exactly one path in T between u and v,
that we denote by uT v. Also, given that uT v has at least 2 vertices, we denote by ůT v
(resp. uT v̊) the path uT v with the vertex u (resp. v) deleted.

Journal of Graph Theory DOI 10.1002/jgt

30 JOURNAL OF GRAPH THEORY

Let C be a cycle on which we fixed some orientation. Then, there is exactly one path
following this orientation between any two vertices u, v ∈ V (C). Similarly, we denote
this path by uCv and we define ůCv and uCv̊ as we did for the tree.
In a rooted tree T with root r, the least common ancestor of two vertices u and v,
written lcaT (u, v) is the first common vertex of the paths uTr and vTr. We refer to the
root of T by the notation root(T ).
For every integer h > 0, we denote by Bh the complete binary tree of height h.

3. RESULTS

We present in this article bounds on the treewidth of graphs not containing the following
parameterized graphs: the wheel of order k (section 5), the double wheel of order k
(section 6), any graph on k vertices and pathwidth at most 2 (section 7) and the yurt
graph of order k (section 8). The definitions of these graphs can be found in the cor-
responding sections. In section 4, we recall some propositions that we will use and
we prove two lemmata which will be useful later. The theorems we then prove are the
following.
Theorem 3.1. Let k > 0 be an integer and G be a graph. If tw(G)  36k − 2, then G
contains a wheel of order k as minor.
Theorem 3.2. Let k > 0 be an integer and G be a graph. If tw(G)  12(8k log(8k) +
2)2 − 4, then G contains a double wheel of order at least k as minor.
Theorem 3.3. Let k > 0 be an integer, G be a graph and H be a graph on k vertices
and of pathwidth at most 2. If tw(G)  3k(k − 4) + 8 then G contains H as minor.
Theorem 3.4. Let k > 0 be an integer and G be a graph. If tw(G)  6k4 − 24k3 +
48k2 − 48k + 23, then G contains the yurt graph of order k as minor.

4. PRELIMINARIES

Proposition 4.1 ([18], (4.3)]). Let k > 0 be an integer, let F be a forest on k vertices
and let G be a graph. If tw(G)  32 k − 1, then G has a separation (A, B) of order k such
that
r G[B \ A] is connected;
r A ∩ B is linked in G[B];
r (A, B) left-contains F.
Proposition 4.2 (Erdös–Szekeres Theorem, [13]). Let k and  be two positive integers.
Then any sequence of ( − 1)(k − 1) + 1 distinct integers contains either an increasing
subsequence of length k or a decreasing subsequence of length .
|L(T )|·diam(T )
Lemma 4.1. For every tree T , |V (T )|  2
+ 1.
Proof. Root T to a vertex r ∈ V (T ) that is halfway  of a longest path of T . For
diam(T )
each leaf x ∈ L(T ), we know that |V (xT r̊)|  2
. Observe that V (T ) = {r} ∪

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 31

x∈L(T ) V (xT r̊). Therefore,

|V (T )|  x∈L(T )|V (xT r̊)| + 1
 
)
|V (T )|  |L(T )| · diam(T
2
+ 1.

Notice that equality holds for the subdivided star (obtained from K1,n by subdividing k
times every edge, for some n, k ∈ N). 
Definition 4.1 (The set (T )). Let T be a tree. We denote by (T ) the set containing
every
√ graph obtained as follows: take the disjoint union of T , a path P where |V (P)| 
|L(T )|, and an extra vertex vnew , and add edges such that
(i) there is an edge between vnew and every vertex of P;
(ii) there are |V (P)| disjoint edges between P and L(T );
(iii) there are no more edges than the edges of T and P and the edges mentioned in
(4.1) and (4.1).
Lemma 4.2. Let n  1 be an integer, T be a tree on n vertices an let G be a graph. If
tw(G)  3n − 1, then H m G for some H ∈ (T ).
Proof. Let n, T , and G be as in the statement of the lemma. Let l be the number of
leaves of T , and let J be a path on l vertices. We consider the disjoint union of J and T .
The graph G has treewidth at least 32 (n + l) − 1, then by Proposition 4.1, G has a
separation (A, B) of order n + l such that
(i) G[B \ A] is connected;
(ii) A ∩ B is linked in G[B];
(iii) (A, B) left-contains the graph J ∪ T .
Let (M, ϕ) be the a model of J ∪ T in G[A] that witnesses (4).
We call the vertices of A ∩ B that belong to ϕ(v) for some v ∈ V (J) the J-part, and
vertices that belong to ϕ(v) for some v ∈ L(T ) forms the L(T )-part. Notice that two
distinct vertices of the J-part (resp. L(T )-part) will be contracted to distinct vertices by
the model.
Let P a set of l disjoint paths with the one endpoint in the J-part and the other in
the L(T )-part, and whose interior belongs to B \ A. The existence of such paths is given
by (4). For each P ∈ P , we arbitrarily choose a vertex vP of the interior of P, that is,
vP ∈ V (P) \ A. By (4), G[B √ \ A] is connected: let Y be a smallest tree spanning the
vertices {vP }P∈P . Let s = |L(T )|, and let Y ∗ be the tree obtained from Y by dissolving
every vertex of degree two that is not vP for some P ∈ P . We are now facing two possible
situations.
Case 1: Y ∗ has a path of length s. Let Q be the path of Y corresponding to a path of
lenght s in Y ∗ and let S be the set of vertices u ∈ V (Q) that are not of degree two or that
are vP for some P ∈ P . Observe that from every u ∈ S, there is a path Ju to the L(T )-part
and a path Ju
to the J-part. Indeed, if u = vP for some P ∈ P , then u is a vertex of P
linking (by definition) a vertex of the L(T )-part to a vertex of the J-part. Otherwise, u is
of degree at least 3 in Y and every leaf of the subtrees of Y \ Q (at least one of which
is adjacent to u), is a vP for some P ∈ P (by minimality of Y ), so is connected to the
L(T )-part and the J-part as explained above. Furthermore, for every two distinct u, v ∈ S,
the aforementioned path are disjoint.

Journal of Graph Theory DOI 10.1002/jgt

32 JOURNAL OF GRAPH THEORY

o2
w1 w2 w1 w2

o o1
w6 w3 w6 w3

w5 w4 w5 w4

FIGURE 1. A wheel of order six (left) and a double wheel of order 6 (right).

Let us now summarize. G[∪v∈V (J) ϕ(v)] is a connected subgraph of G, which is con-

nected by the s disjoint paths Juu∈S to the path Y . All the endpoints of the paths Juu∈S on
Y are connected by s disjoint paths Juu∈S to the L(T )-part, which correspond to the leaves
in a model of T . Therefore this graph contains a member of (T ) as a minor, as required.
Case 2: diam(Y ∗ ) < s. From Lemma 4.1, |L(Y )| = |L(Y ∗ )|  s. Observe that L(Y ) ⊆
{vP }P∈P (this follows by the minimality of Y ). Let S = V (Y ) \ L(Y ). We consider the
minor of G obtained by contracting, for every P ∈ P such that vP ∈ L(Y ), every edge
of the subpath connecting the J-part to a leaf of Y . In this graph, S induces a connected
subgraph adjacent to at least s distinct vertices of the J-part. All these s vertices of the
J-part are connected by s disjoint paths to distinct vertices of the L(T )-part. Thus this
contains a member of (T ) as a minor, and so do G. 

5. EXCLUDING A WHEEL WITH A LINEAR BOUND ON TREEWIDTH

Definition 5.1. (wheel). Let r > 2 be an integer. The wheel of order r (denoted Wr ) is
a cycle of length r whose each vertex is adjacent to an extra vertex, in other words it is a
the graph of the form
V (G) = {o, w1 , . . . , wr }
E(G) = {{w1 , w2 } , {w2 , w3 } , . . . , {wr−1 , wr } , {wr , w1 }} ∪ {{o, w1 } , . . . , {o, wr }}
(see Fig. 1 for an example).
Lemma 5.1. Let h > 2 be an integer. Let G be a graph obtained from the union of
the tree T = Bh and a path P by adding the edges {l, ψ (l)} ∈ E(G) for every l ∈ L(T ),
where ψ : L(T ) → V (P) is a bijection. Then G contains a wheel of order 2h−2 + 1 as a
minor.
Proof. Let h, ψ, T , P = p1 . . . p2h and G be as above. Let r be the root of T .
In the arguments to follow, if t ∈ V (T ), we denote by Tt the subtree of T rooted at t
(i.e. the subtree of T whose vertices are all the vertices t
∈ V (T ) such that the path t
Tr
contains t).
We consider the vertices u = ψ −1 (p1 ) ∈ L(T ) and v = ψ −1 (p2h ) ∈ L(T ) and w =
lcaT (u, v) ∈ V (T ) \ L(T ).
Let τ be a largest subtree of T which is disjoint from uT v. Let Lτ = L(τ ) ∩ L(T ) and
let Q = ψ (Lτ ) ⊆ P. It is not hard to see that G contains W|Q|+1 as a minor. Indeed, the
paths P and uT v together with the edges {p1 , u} and {p2h , v} form a cycle in G. Besides,
the tree τ , which is disjoint from this cycle, has at least |Q| + 1 vertices that are adjacent

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 33

to distinct vertices of P: |Q| of them are the elements of Q, and the other one is the (only)
vertex of τ adjacent to uT v (which exists by maximality of τ ). In the subgraph of G
induced by V (P) ∪ V (uT v) ∪ V (τ ), contracting τ to a vertex gives a vertex adjacent to
at least |Q| + 1 vertices of a (non necessarily induced) cycle, a graph containing W|Q|+1
as subgraph.
Depending on G, |Q| may take different values. However, we show that it is never
less than 2h−2 . Remember, |Q| is the number of leaves that a largest subtree of T that is
disjoint from uT v shares with T . The root r of T has two children r1 and r2 , inducing two
subtrees Tr1 and Tr2 of T . Recall, w = lcaT (u, v).
Case 1. w = r. As w = r, w is a vertex of one of {Tr1 , Tr2 }, say Tr1 , which contains also
u and v, and thus the path uT v. The other subtree Tr2 is then disjoint from uT v, it has
height h − 1 and is complete so it has 2h−1 leaves. Consequently, in this case |Q|  2h−1 .
Case 2. w = r. In this case, the path uT v contains r (and r = u, r = v as u and v are
leaves) so u and v are not in the same subtree of {Tr1 , Tr2 } and uT v contains the two edges
{r, r1 } and {r, r2 }. For every i ∈ {1, 2}, we denote by ri,1 and ri,2 the two children of ri
in T . We assume without loss of generality that u ∈ V (Tr1,1 ) and v ∈ V (Tr2,1 ) (if not, we
just rename the ri ’s ans ri, j ’s). Notice that the path uT v is the concatenation of the paths
uTr1 r1 , r1 Tr2 , r2 Tr2 v. Since the tree Tr1,2 is disjoint from uT v, is complete and is of height
h − 2, it has 2h−2 leaves. Therefore we have |Q|  2h−2 .
In both cases, |Q|  2h−2 and according to what we proved before, G contains a model
of W|Q|+1 . As every wheel contains as a minor every smaller wheel, we proved that G
contains a wheel of order at least 2h−2 . 
Theorem 5.1. Let k > 0 be an integer and G be a graph. If tw(G)  36k − 2, then G
contains a Wk -model.
Proof. Let k > 0 be an integer, G be a graph such that tw(G)  36k − 2, and let
h = log 4k . Since every wheel contains a model of every smaller wheel, we have
Wk m W2log k +1
m W2(log 4k)−2 +1
m W2h−2 +1 .
Therefore, if we prove that G contains a W2h−2 +1 -model, then we are done because
the minor relation is transitive. Let Yh− be the graph of the following form: the disjoint
union of the complete binary tree Bh of height h with leaves set YL and of the path YP on
2h vertices, and let Yh be the set of graphs of the same form, but with the extra edges
{{l, φ(l)}}l∈YL , where φ : YL → V (YP ) is a bijection. As we proved in Lemma 5.1 that
every graph in Yh contains the wheel of order 2h−2 + 1 as minor, showing that G contains
an element of Yh as minor suffices to prove this lemma. That is what we will do.
From our initial assumption, we deduce the following.
5
tw(G)  36k −
2
3
(3 · 2log 8k − 1) − 1

2
3
 (3 · 2log 4k+1 − 1) − 1
2
3
tw(G)  (3 · 2h − 1) − 1.
2
Journal of Graph Theory DOI 10.1002/jgt
34 JOURNAL OF GRAPH THEORY

According to Proposition 4.1, G has a separation (A, B) of order 3 · 2h − 1 such that

(i) G[B \ A] is connected;

(ii) A ∩ B is linked in G[B];
(iii) (A, B) left-contains the graph Yh− .

By definition of left-contains, G[A] contains a model (M− , ϕ − ) of Yh− and every

element of M− contains exactly one element of A ∩ B. For every x ∈ A ∩ B, we denote
by Mx− the element of M− that contains x. Let L (resp. R) be the subset of A ∩ B of
vertices that belong to an element of M related to the leaves of Bh in Yh− (resp. to the path
P). We remark that these sets are both of cardinality 2h .
Since A ∩ B is linked in G[B] (see (5)), there is a set P of 2h disjoint paths between the
vertices of L and the elements of R. Let ψ : L → V (P) be the function that match each
element l of L with the (unique) element of R it is linked to by a path (that we call Pl ) of
P . Observe that ψ is a bijection. We set

∀l ∈ L, Ml = Ml− ∪ V (l Pl ψ ˚(l))
∀r ∈ (A ∩ B) \ L, Mr = Mr−

M= Mx .
x∈A∪B

Let us show that M allows us to define a model of some H ∈ Yh . Let us consider the
following mapping.

V (Yh− ) → M
ϕ: (2)
x → Mx

We claim that (M, ϕ) is a model of H for some H ∈ Yh . This is a consequence of the

following remarks. 

Remark 5.1. Every element of M is either an element of M− , or the union of a

element M of M− and of the vertices of a path that start in M, thus every element of M
induces a connected subgraph of G.

Remark 5.2. The paths of P are all disjoint and are disjoint from the elements of M− .
Every interior of path of P is in but one element of M, therefore the elements of M are
disjoint.

Remark 5.3. The elements {ml }l∈L are in bijection with the elements of {mr }r∈R (thanks
to the function ψ) and every two vertices l ∈ L and ψ (l) ∈ R are such that there is an
edge between ml and mψ (l) (by definition of M+ ).

We just proved that (M, ϕ) is a model of a graph of Yh in G. Finally, we apply

Lemma 5.1 to find a model of the wheel of order 2h−2 + 1 = 2log k−2 + 1  k in G and
this concludes the proof.

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 35

6. EXCLUDING A DOUBLE WHEEL WITH A (l log l )2 BOUND

ON TREEWIDTH

Definition 6.1. (double wheel). Let r > 2 be an integer. The double wheel of order r
(denoted W2r ) is a cycle of length r whose each vertex is adjacent to two different extra
vertices, in other words it is the graph of the form
V (G) = {o1 , o2 , w1 , . . . , wr }
E(G) = {{w1 , w2 } , {w2 , w3 } , . . . , {wr−1 , wr } , {wr , w1 }}
∪ {{o1 , w1 } , . . . , {o1 , wr }}
∪ {{o2 , w1 } , . . . , {o2 , wr }}
(see Fig. 1 for an example).
Lemma 6.1. Let G be a graph and h > 0 be an integer. If tw(G)  6 · 2h − 4, then G
h
2 2 −2
contains as minor a double wheel of order at least 2h−3
.
Proof. Let h and G be as above. Observe that tw(G)  3(2h+1 − 1) − 1. As the
binary tree T = Bh has 2h+1 − 1 vertices, G contains a graph H ∈ (Bh ) as minor (by
Lemma 4.2). Let us show that any graph H ∈ (Bh ) contains a double wheel of order at
h
2 −2
least 22h−3 as minor.
h
Let P be the path of length at least 2 2 in the definition of H. Let L be the set, of size at
h
least 2 2 , of the leaves of T that are adjacent to P in H. Such a set exists by definition of
(Bh ). We also define u (resp. u
) as the vertex of L(T ) that is adjacent to one end of P
(resp. to the other end of P) and Q = uTu
.
As T is a binary tree of height h, Q has at most 2h − 1 vertices. Each vertex of Q is of
degree at most 3 in T except the two ends which are of degree 1. Consequently, T \ Q
has at most 2h − 3 connected components that are subtrees of T. Notice that every vertex
h
of the 2 2 elements of L is either a leaf of one of these 2h − 3 subtrees, or one of the two
ends of Q. By the pigeonhole principle, one of these subtrees, which we call T1 , has at
h
2 −2
least 22h−3 leaves that are elements of L.
Let Mo1 be the set of vertices of this subtree T1 . We also set Mo2 = {vnew } (cf. Defini-
tion 4.1 for a definition of vnew ). Let us consider the cycle C made by the concatenation
of the paths uPu
and u
Tu in H.
h
2 −2
By definition of Mo1 , there are at least 22h−3 vertices of C adjacent to vertices of Mo1 .

Let J = j1 , . . . , j|J| be the set of such vertices of C, in the same order as they appear
h
2 −2
in C (we then have |J|  22h−3 ).
We arbitrarily choose an orientation of C and define the sets of vertices
M1 , M2 , . . . , M|J| as follows.
∀i ∈ [[1, |J| − 1]], Mi = V ( jiC ji+1
˚ )
M|J| = V ( j|J|C j˚1 ).

Let M = M1 , . . . , M|J| , Mo1 , Mo2 and ψ : V (W2|J| ) → M be the function defined
by
∀i ∈ [[1, |J|]], ψ (wi ) = Mi

Journal of Graph Theory DOI 10.1002/jgt

36 JOURNAL OF GRAPH THEORY

ψ (o1 ) = Mo1
ψ (o2 ) = Mo2 .
Notice that ψ maps the vertices of W2|J| to connected subgraphs of H such that ∀(v, w) ∈
E(W2|J| ), there is a vertex of ψ (v) adjacent in H to a vertex of ψ (w). Therefore, (M, ψ )
is a W2|J| -model in H.
h h
2 −2 2 2 −2
Since |J|  22h−3 , H contains a double wheel of order at least 2h−3
, which is what we
wanted to show. 
Corollary 6.1. Let l > 0 be an integer and √
G be a graph. If tw(G)  12l − 4 then G
l−2
contains a double wheel of order at least 2 log l−5 as minor.
Proof. Let l and G be as above. First remark that
log l − 1  log l  log l . (3)
Our initial assumption on tw(G) gives the following.
tw(G)  12l − 4
 6 · 2log(2l) − 4
 6 · 2log l+1 − 4
 6 · 2log l − 4. by (3)
By Lemma 6.1, G contains a double wheel of order at least
log l
2 2 −2
q=
2 log l − 3
1
2 2 log l − 2
 by (3)
2(log l − 1) − 3
√
l−2

2 log l − 5
√
Therefore, G contains a double wheel of order q  l−2
2 log l−5
, as required. 
Theorem 6.1 (follows from Corollary 6.1). Let k > 0 be an integer and G be a graph.
If tw(G)  12(8k log(8k) + 2)2 − 4, then G contains a double wheel of order at least k
as minor.
Proof. Applying Corollary 6.1 for l = (8k log(8k) + 2)2 yields that G contains a
double wheel of order at least
√
l−2
q
2 log l − 5
8k log(8k)

4 log(8k log(8k) + 2) − 5
8k log(8k)

4 log(8k log(8k)) − 1
8k log(8k)

4(log(8k) + log log(8k)) − 1

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 37

x0 x1 x2 x3 x4

y0 y1 y2 y3 y4

z0 z1 z2 z3 z4

FIGURE 2. The graph 5

8k log(8k)

8 log(8k) − 1
k
Consequently G contains a double wheel of order q  k and we are done. 

7. EXCLUDING A GRAPH OF PATHWIDTH AT MOST 2 WITH

A QUADRATIC BOUND ON TREEWIDTH

Definition 7.1. (graph r ). We define the graph r as the graph of the following form
(see Fig. 2).

V (G) = {x0 , . . . , xr−1 , y0 , . . . , yr−1 , z0 , . . . , zr−1 }
E(G) = {{xi , xi+1 } , {zi , zi+1 }}i∈[[1,r−1]] ∪ {{xi , yi } , {yi , zi }}i∈[[0,r−1]]

A. Graphs of Pathwidth 2 in r
Instead of proving that a treewidth quadratic in |V (H )| forces an H-minor for every graph
H of pathwidth at most 2, we prove that a treewidth quadratic in r forces an r -minor
and then that every graph of pathwidth at most 2 on r vertices is minor of r . For this,
we first need some lemmata and remarks about path decompositions.
Definition 7.2 (nice path decompostion, [17]).

A path decomposition (p1 p2 . . . pk ,
{Xpi }i∈[[1,k]] ) of a graph G is said to be nice if
Xp1
= 1 and

∀i ∈ [[2, k]],
(Xpi \ Xpi−1 ) ∪ (Xpi−1 \ Xpi )
= 1.
It is known [7] that every graph have an optimal path decomposition which is nice and

in such
decomposition, every node
Xi is either
an introduce node (i.e. either i = 1 or
that

Xp \ Xp
= 1) or a forget node (i.e.
Xp \ Xp
= 1).
i i−1 i−1 i

Remark 7.1. It is easy to observe that for every graph G on n vertices, there is an
optimal path decomposition with n introduce nodes and n forget nodes (one of each for
each vertex of G), thus of length 2n.

Remark 7.2. Let G be a graph and let (p1 p2 . . . pk , X ), X = Xpi i∈[[1,k]] be a nice (non
necessarly optimal) path decomposition of G. Let
w be
the width of this decomposition.
For every i ∈ [[2, k − 1]], if pi is a forget node,
Xpi
 w − 1 and pi+1 is an introduce
node, then by setting
Xp
i = Xpi−1 ∪ Xpi+1

Journal of Graph Theory DOI 10.1002/jgt

38 JOURNAL OF GRAPH THEORY

∀ j ∈ [[1, k]], j = i, Xp
j = Xp j
 
X
= Xp
j
j∈[[1,k]],

we create from (p1 p2 . . . pk , X ) a valid path decomposition

of
G, where pi is now an
introduce node and pi+1 a forget node. Observe that
Xp
i

Xpi
+ 2 = w + 1 Therefore
the

new
path decomposition has the same width as the original one. Note that the condition

Xp
 w − 1 holds, for instance, when pi−1 is required to be a forget node too (for
i
i ∈ [[3, k − 1]]).
Remark 7.3. Let G be a graph and P = (p1 p2 . . . pk , X ) be a nice path decomposition
of G. For every i ∈ [[1, k]], the path p1 . . . pi contains at most as many forget nodes as
introduce nodes and the difference between these two numbers is at most w + 1 where w
is the width of P.
Lemma 7.1. Let G be a graph on n vertices . Then G has an optimal path decomposition
P such that
(i) every bag of P has size pw(G) + 1;
(ii) every two adjacent bags differs by exactly one element, i.e. for every two adjacent
vertices u and v of P, |Xu \ Xv | = |Xv \ Xu | = 1.
Proof. Let P = (p1 p2 . . . p2k , X ) with X = {Xpi }i∈[[1,2k]] be a nice optimal path
decomposition of G with as many introduce nodes (resp. forget nodes) as there are
vertices in G.
Let s = pw(G) + 1. According to Remarks 7.2 and 7.3, P can be modified into a path
decomposition of G of the same width and such that
(a) the s first vertices of P are introduce nodes and ps+1 is a forget node;
(b) the s last vertices of P are forget nodes and p2k−s is an introduce node;
(c) for every i ∈ [[s, 2k − s]], pi and pi+1 are nodes of different type.
In the arguments to follow, we assume that P satisfies this property. 
Remark 7.4. Introduce nodes all have bags of cardinality s.
Remark 7.5. For every i ∈ [[0, k − s]], the node ps+2i is an introduce node and the
node ps+2i+1 is a forget node, which implies Xps+2i  Xps+2i+1 . Also note that for every
i ∈ [[1, s − 1]], Xpi  Xps and for every i ∈ [[2k − s + 1, 2k]], Xpi  Xp2k−s .
Intuitively, every bag X that is included in one of its adjacent bags X
contains no more
information than what X
already contains, so we will just remove it.
We thus define P
= ps ps+2 . . . ps+2i . . . p2k−s (a path made of all introduce nodes of
P). Clearly, P and P
have the same width and as we deleted only redundant nodes, P
is
still a valid path decomposition of G.
Since every two adjacent nodes of P
were introduce nodes separated by a forget node
in P, they only differ by one element. According to Remark 7.4 and since every node of
P
was an introduce node in P, every bag of P
have size pw(G) + 1. Consequently, P
is
an optimal path decomposition that satisfies the conditions of the lemma statement.
Remark 7.6. The path decomposition of Lemma 7.1 has length V (G) − pw(G).
Proof. Let (P, X ) be such a path decomposition. Remember that the first node of
P has a bag of size pw(G) + 1 and that every two adjacent nodes of P have bags which

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 39

differs by exactly one element. Since every vertex of G is in a bag of P, in addition to

the first bag containing pw(G) + 1 vertices of G, P must have V (G) − pw(G) − 1 other
bags in order to contain all vertices of G. Therefore P has length V (G) − pw(G). 
A proof of a slightly weaker version of the following lemma previously appeared [20].
Lemma 7.2. For every graph G on n vertices and of pathwidth at most 2, there is a
minor model of G in n−1 .
Proof. Let G be as in the statement of the lemma. We assume that pw(G) = 2 (if
this is not the case we add edges to G in order to obtain a graph of pathwidth 2 which
contains G as a minor). Let r = V (G) − pw(G) = n − 2.
Let P = (p1 . . . pr , Xp1 , . . . , Xpr ) be an optimal path decomposition of G satisfy-
ing the properties of Lemma 7.1, of length r. Such decomposition exists according to
Lemma 7.1 and Remark 7.6).
Using this decomposition, we will now define a labeling λ of the vertices of r+1 .
When dealing with the vertices of r+1 we will use the notations defined in Definition 7.1.
Let λ : V ( r+1 ) → V (G) be the function defined as follows:
(a) λ(x0 ) and λ(y0 ) are both equal to one (arbitrarily chosen) element of the set
Xp1 ∩ Xp2 ;
(b) λ(z0 ) is equal to the only element of the set Xp1 ∩ Xp2 \ {λ(x1 )};
(c) ∀i ∈ [[2, r]], λ(yi ) = Xpi \ Xpi−1 and we consider two cases:
Case 1: Xpi−1 ∩ Xpi = Xpi ∩ Xpi+1
λ(xi ) = λ(xi−1 ) and λ(zi ) = λ(zi−1 );
Case 2: Xpi−1 ∩ Xpi = Xpi ∩ Xpi+1
if Xpi−1 ∩ Xpi ∩ Xpi+1 = λ(xi−1 ),
then λ(xi ) = λ(xi−1 ) and λ(zi ) = Xpi \ Xpi−1 ;
else λ(xi ) = Xpi \ Xpi−1 and λ(zi ) = λ(zi−1 ).
Thanks to this labeling, we are now able to present a minor model of G in r+1 :
∀v ∈ V (G), Mv = {u ∈ V ( r+1 ), λ(u) = v}
M = {Mv }v∈V (G)

V (G) → M
ϕ:
u → Mu .
To show that (M, ϕ) is a G-model in r+1 , we now check if it matches the definition
of a minor model.
By definition, every element of M is a subset of V ( r+1 ). To show that every element
of M induces a connected subgraph in G, it suffices to show that nodes of r+1 which
have the same label induces a connected subgraph in G (by construction of the elements
of M). This can easily be seen by remarking that for every i ∈ [[2, r]], every vertex yi of
r+1 gets a new label and that every vertex xi (resp. zi ) of r+1 receive either the same
label as yi , or the same label as xi−1 (resp. zi−1 ).
Let us show that this labeling ensure that if two vertices u and v of G are in the same
bag of P, there are two adjacent vertices of r+1 that respectively gets labels u and v.
Let u, v be two vertices of G which are in the same bag of P. Let i be such that Xi is
the first bag of P (with respect to the subscripts of the bags of P) which contains both
u and v. The case i = 1 is trivial so we assume that i > 1. We also assume without loss

Journal of Graph Theory DOI 10.1002/jgt

40 JOURNAL OF GRAPH THEORY

first half of P second half of P

FIGURE 3. Example for Lemma 7.3

of generality that Xi \ Xi−1 = {v}, what gives λ(yi ) = v. Depending on in what case we
are, either either λ(xi ) = u (A.) or λ(zi ) = u (A. and A.). In both cases, u and v are
the labels of two adjacent nodes of r+1 . By construction of the elements of M, this
implies that if {u, v} ∈ E(G), then there are vertices u
∈ ϕ(u) and v
∈ ϕ(v) such that
{u
, v
} ∈ E( r+1 ).
Therefore, (M, ϕ) is a G-model in n−1 , what we wanted to find. 

B. Exclusion of r

Lemma 7.3. For any graph, if tw(G)  3 − 1 then G contains as minor the following
graph: a path P = p1 . . . p2 of length 2 and a family Q of  paths of length 2 such that
every vertex of P is the end of exactly one path of Q and every path of Q has one end in
p1 . . . pl (the first half of P) and the other end in pl+1 . . . p2l (the second half of P) (see
Fig. 3 ).
Proof. Let  > 0 be an integer and G be a graph of treewidth at least 3 − 1.
According to Proposition 4.1, G has a separation (A, B) of order 2 such that

(i) G[B \ A] is connected;

(ii) A ∩ B is linked in G[B];
(iii) (A, B) left-contains a path P = p1 . . . p2 of length 2.

Let (M, ϕ) be a model of P in G[A], with M = {M1 , . . . , M2 }. We assume without

loss of generality that ϕ maps pi to Mi for every i ∈ [[1, 2]].
As A ∩ B is linked in G[B], there is a set Q of  disjoint paths
 in G[B] of length at least
2 and such that every path q ∈ Q has one end in (A ∩ B) ∩ i∈[[1,]] Mi , the other end in
(A ∩ B) ∩ i∈[[+1,2]] Mi and its internal  in A ∩ B.
vertices are not 
Let G
be the graph obtained from G[( q∈Q V (q)) ∪ ( M∈M M)] after the following
operations.

(1) iteratively contract the edges of every path of Q until it reaches a length of 2. The
paths of Q have length at least 2, so this is always possible.
(2) for every i ∈ [[1, 2]], contract Mi to a single vertex. The elements of a model are
connected (by definition) thus this operation can always be performed.

As one can easily check, the graph G

is the graph we were looking for and it has been
obtained by contracting some edges of a subgraph of G, therefore G
m G. 
Theorem 7.1. Let G be a graph and H be a graph on h vertices satisfying pw(H )  2.
If tw(G)  3(h − 2) − 1 then G contains H as a minor.

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 41

FIGURE 4. The yurt graph of order 5, Y5

Proof. Let G, H and h be as in the statement of the Lemma. According to Lemma 7.2,
every graph of pathwidth at most two on n vertices is minor of n−1 . Therefore in order
to show that G m H it is enough to prove that G m h−1 . This is what we will do.
According to Lemma 7.3, G contains as minor two paths P = p1 . . . p(h−2) and R =
r1 . . . rh−2) and a family Q of (k − 2) paths of length 2 such that every vertex of P
or R is the end of exactly one path of Q and every path of Q has one end in P and
the other end in R. For every p ∈ P, we denote by ϕ(p) the (unique) vertex of R to
which p is linked to by a path of Q. Observe that ϕ is a bijection. By Proposition 4.2,
there is a subsequence P
= (p
1 , p
2 , . . . , p
h−1 ) of the vertices of P such that the vertices
ϕ(p
1 ), ϕ(p
2 ), . . . , ϕ(p
h−1 ) appear in R either in this order or in the reverse order. Let
R
= (ϕ(p
1 ), ϕ(p
2 ), . . . , ϕ(p
h−1 )) and Q
be the set of inner vertices of the paths from
p
i to ϕ(p
i ) for all i ∈ [[1, h − 1]].
Iteratively contracting in G which have at most one end in P
(resp. in R
) and removing
the vertices that are not in P
, R
or Q
gives the graph h−1 . The operations used to obtain
it are vertices and edge deletions, and edge contractions, thus h−1 is a minor of G. This
concludes the proof. 

8. EXCLUDING A YURT GRAPH

Definition 8.1. (yurt graph of order r). Let r > 0 be an integer. In this article, we call
yurt graph of order r the graph Yr of the form
V (Yr ) = {x1 , . . . , xr , y1 , . . . , yr , o}

E(Yr ) = {xi , xi+1 }i∈[[1,r−1]]

∪ {yi , yi+1 }i∈[[1,r−1]]
∪ {{xi , yi }}i∈[[1,r]]
∪ {{yi , o}}i∈[[1,r]]
(see Fig. 4 for an example).
For every r > 0, we define the comb of order r as the tree made from the path
p1 p2 . . . pr and the extra vertices v1 , v2 , . . . , vr by adding an edge between pi and vi for
every i ∈ [[1, r]].
Theorem 8.1. Let k > 0 be an integer and G be a graph. If tw(G)  6k4 − 24k3 +
48k2 − 48k + 23, then G contains Yk as minor.
Proof. Let k > 0 be an integer and G be a graph such that tw(G)  6k4 −
24k3 + 48k2 − 48k + 23. Let C be the comb with l = k4 − 4k3 + 8k2 − 8k + 4 teeth.
As tw(G)  3 |V (C)| − 1, G contains some graph of (C) by Lemma 4.2.

Journal of Graph Theory DOI 10.1002/jgt

42 JOURNAL OF GRAPH THEORY

Let us prove that every graph of (C) contains the yurt graph of order k. Let H be a
graph of (C). We respectively call T , P and o the tree, path and extra vertex of (C).
Let F be the subset of edges between P and the leaves of T
Let L = l0 , . . . , lk2 −2k+2 (resp. Q = q0 , . . . , qk2 −2k+2 ) be the leaves of T (resp. of P)that
are the end of an edge of F We assume without loss of generality that they appears in
this order.
According to Proposition 4.2, there is a subsequence Q
of Q of length k such that the
corresponding vertices L
of L appear in the same order. As one can easily see, this graph
contains the yurt of order k and we are done. 

9. DISCUSSION AND OPEN PROBLEMS

An natural question is whether the results of this article for the classes Hki , i ∈ {1, . . . , 3}
are tight. This is indeed the case for the wheels in Hk1 as (1) does not hold for any
pair of the form (Hk1 , f (k)) where f = o(k). To see this, it is enough to observe that a
clique Kk does not contain any wheel on k + 1 vertices as a minor while has treewidth
k − 1 = (k). Clearly, the same lower bound holds for Hk2 (i.e., the double wheels).
It is easy to prove that (1) does not hold for any pair of the form (Hk0 , f (k)) or
(Hk3 , f (k)) when f = o(k log k). To see this, consider a (large enough) n-vertex 3-regular
Ramanujan graph R (see [19]). Such a graph has girth at least c log n for some univer-
sal constant c (see [3]), and satisfies tw(R) = (n) (cf. [1, Corollary 1]). Let k
be
the minimum integer such that n < k
· c log n holds. Notice that n = (k
log k
), thus
tw(R) = (k
log k
). We will show that no graph of H2k 0

∪ H2k
is a minor of R. As every
3

graph of H2k
∪ H2k
contains k · K3 as a minor, it is enough to show that k
· K3 is not
0 3

a minor of R. If k
· K3 is a minor of R, then R contains a collection of k
vertex-disjoint
cycles. As the girth of R is at least c log n, we have that n  k
· c log n, a contradiction.
The above observation implies that the function f (k) = (k log k) is the best for
which (1) may hold for the pairs (Hk0 , f (k)) and (Hk3 , f (k)) and we conjecture that this
is indeed the case. Observe that, by the same remark, the lower bound (k log k) also
holds for any class {Hk }k∈N such that for every k ∈ N, Hk contains as a minor (k) vertex
disjoint cycles. Interestingly, the above proof does not apply for the double wheels in Hk2 .
This tempts us to conjecture that (1) holds (optimally) for the pair (Hk2 , k).

ACKNOWLEDGMENT

We thank Konstantinos Stavropoulos for bringing the results in [18] (and, in particular,
Proposition 4.1) to our attention, during Dagstuhl Seminar 11071.

REFERENCES
[1] S. Bezrukov, R. Elsässer, B. Monien, R. Preis, and J.-P. Tillich, New spectral
lower bounds on the bisection width of graphs, Theoret Comp Sci 320(2–3)
(2004), 155–174.
[2] D. Bienstock, N. Robertson, P. Seymour, and R. Thomas, Quickly excluding
a forest, J Combin Theory Ser B 52(2) (1991), 274–283.

Journal of Graph Theory DOI 10.1002/jgt

 LOW POLYNOMIAL EXCLUSION OF PLANAR GRAPH PATTERNS 43

[3] N. Biggs and A. Boshier, Note on the girth of ramanujan graphs, J Combin
Theory Ser B 49(2) (1990), 190–194.
[4] E. Birmelé, J. Bondy, and B. Reed, Brambles, prisms and grids, In: Graph
Theory in Paris, Trends in Mathematics (A. Bondy, J. Fonlupt, J.-L. Fouquet,
J.-C. Fournier, and J. L. Ramı́rez Alfonsı́n, Eds.), Birkhäuser, Basel, 2007,
pp. 37–44.
[5] H. L. Bodlaender, On linear time minor tests with depth-first search, J Algo-
rithms 14(1) (1993), 1–23.
[6] H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth.
Theoret Comput Sci 209(1-2) (1998), 1–45.
[7] H. L. Bodlaender and D. M. Thilikos, Computing small search numbers in
linear time, in: Parameterized and Exact Computation, Proceedings of the
First International Workshop (IWPEC 2004), in: LNCS (D. Rod, F. Michael,
and D. Frank, Eds.), vol. 3162, Springer, Berlin Heidelberg, 2004, pp. 37–48.
[8] H. L. Bodlaender, J. van Leeuwen, R. B. Tan, and D. M. Thilikos, On interval
routing schemes and treewidth, Inf Comput 139(1) (1997), 92–109.
[9] C. Chekuri and J. Chuzhoy, Polynomial bounds for the grid-minor theorem,
CoRR (2013), abs/1305.6577.
[10] E. D. Demaine and M. Hajiaghayi, Linearity of grid minors in treewidth with
applications through bidimensionality, Combinatorica 28(1) (2008), 19–36.
[11] E. D. Demaine, M. Hajiaghayi, and K. Kawarabayashi, Algorithmic graph
minor theory: Improved grid minor bounds and Wagner’s contraction, Algo-
rithmica, 54(2) (2009), 142–180.
[12] R. Diestel, T. R. Jensen, K. Y. Gorbunov, and C. Thomassen, Highly connected
sets and the excluded grid theorem, J Combin Theory Ser B 75(1) (1999),
61–73.
[13] P. Erdős and G. Szekeres, A combinatorial problem in geometry. In: Classic
Papers in Combinatorics, Modern Birkhäuser Classics (I. Gessel and G.-C.
Rota, Eds.), Birkhäuser , Boston, 1987, pp. 49–56.
[14] M. R. Fellows and M. A. Langston, On search, decision, and the effi-
ciency of polynomial-time algorithms, J Comput Syst Sci 49(3) (1994), 769–
779.
[15] F. V. Fomin, D. Lokshtanov, and S. Saurabh, Bidimensionality and geometric
graphs, in: Proceedings of the Twenty–third Annual ACM-SIAM Symposium
on Discrete Algorithms, SIAM, Kyoto, Japan, 2012, pp. 1563–1575.
[16] K. ichi Kawarabayashi and Y. Kobayashi, Linear min-max relation be-
tween the treewidth of H-minor-free graphs and its largest grid, in: C.
Dürr and T. Wilke (Eds.), 29th International Symposium on Theoreti-
cal Aspects of Computer Science (STACS 2012), in: Leibniz International
Proceedings in Informatics (LIPIcs), vol. 14, Dagstuhl, Paris, France,
2012, pp. 278–289. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
doi: 10.4230/LIPIcs.STACS.2012.278
[17] T. Kloks, Treewidth, Computations and Approximations, LNCS, 842,
Springer, Berlin Heidelberg, 1994.

Journal of Graph Theory DOI 10.1002/jgt

44 JOURNAL OF GRAPH THEORY

[18] A. Leaf and P. Seymour, Tree-width and planar minors. Journal of Combi-
natorial Theory, Series B Manuscript, vol. 111, 2012, 38–53, http://www.
sciencedirect.com/science/article/pii/S0095895614001038.
[19] M. Morgenstern, Existence and explicit constructions of q + 1 regular ra-
manujan graphs for every prime power q, J Combin Theory Ser B 62(1)
(1994), 44–62.
[20] A. Proskurowski, Maximal Graphs of Path-width K or Searching a Partial K-
caterpillar, University of Oregon Department of Computer and Information
Science, 1989.
[21] N. Robertson and P. D. Seymour, Graph minors, II. Algorithmic aspects of
tree-width, J Algorithms 7 (1986), 309–322.
[22] N. Robertson and P. D. Seymour, Graph minors, V. Excluding a planar graph,
J Combin Theory Ser B 41(2) (1986), 92–114.
[23] N. Robertson, P. D. Seymour, and R. Thomas, Quickly excluding a planar
graph, J Combin Theory Ser B 62(2) (1994), 323–348.

Journal of Graph Theory DOI 10.1002/jgt