  Alon, Seymour, and Thomas generalized Lipton and Tarjan's planar separator
theorem and showed that a $K_h$-minor free graph with $n$ vertices has a
separator of size at most $h^{3/2}\sqrt n$. They gave an algorithm that, given
a graph $G$ with $m$ edges and $n$ vertices and given an integer $h\geq 1$,
outputs in $O(\sqrt{hn}m)$ time such a separator or a $K_h$-minor of $G$.
Plotkin, Rao, and Smith gave an $O(hm\sqrt{n\log n})$ time algorithm to find a
separator of size $O(h\sqrt{n\log n})$. Kawarabayashi and Reed improved the
bound on the size of the separator to $h\sqrt n$ and gave an algorithm that
finds such a separator in $O(n^{1 + \epsilon})$ time for any constant $\epsilon
> 0$, assuming $h$ is constant. This algorithm has an extremely large
dependency on $h$ in the running time (some power tower of $h$ whose height is
itself a function of $h$), making it impractical even for small $h$. We are
interested in a small polynomial time dependency on $h$ and we show how to find
an $O(h\sqrt{n\log n})$-size separator or report that $G$ has a $K_h$-minor in
$O(\poly(h)n^{5/4 + \epsilon})$ time for any constant $\epsilon > 0$. We also
present the first $O(\poly(h)n)$ time algorithm to find a separator of size
$O(n^c)$ for a constant $c < 1$. As corollaries of our results, we get improved
algorithms for shortest paths and maximum matching. Furthermore, for integers
$\ell$ and $h$, we give an $O(m + n^{2 + \epsilon}/\ell)$ time algorithm that
either produces a $K_h$-minor of depth $O(\ell\log n)$ or a separator of size
at most $O(n/\ell + \ell h^2\log n)$. This improves the shallow minor algorithm
of Plotkin, Rao, and Smith when $m = \Omega(n^{1 + \epsilon})$. We get a
similar running time improvement for an approximation algorithm for the problem
of finding a largest $K_h$-minor in a given graph.
