  One of the key results in Robertson and Seymour's seminal work on graph
minors is the Grid-Minor Theorem (also called the Excluded Grid Theorem). The
theorem states that for every grid $H$, every graph whose treewidth is large
enough relative to $|V(H)|$ contains $H$ as a minor. This theorem has found
many applications in graph theory and algorithms. Let $f(k)$ denote the largest
value such that every graph of treewidth $k$ contains a grid minor of size
$(f(k)\times f(k))$. The best previous quantitative bound, due to recent work
of Kawarabayashi and Kobayashi, and Leaf and Seymour, shows that
$f(k)=\Omega(\sqrt{\log k/\log \log k})$. In contrast, the best known upper
bound implies that $f(k) = O(\sqrt{k/\log k})$. In this paper we obtain the
first polynomial relationship between treewidth and grid minor size by showing
that $f(k)=\Omega(k^{\delta})$ for some fixed constant $\delta > 0$, and
describe a randomized algorithm, whose running time is polynomial in $|V(G)|$
and $k$, that with high probability finds a model of such a grid minor in $G$.
