Graphs excluding a fixed minor

Families of graphs that exclude a fixed minor H have all kinds of nice properties: for example

• If G excludes a fixed minor H, then G has O(n) edges
• If G excludes a fixed minor H, then G has O(\sqrt{n}) treewidth
• If G excludes a fixed minor H, then G has a nice decomposition into a few graphs of small treewidth
• If G excludes a fixed minor H, then G can be decomposed into a clique sum of graphs that are almost embeddable on surfaces of bounded genus.

(all of these and more in Jeff Erickson's excellent comp. topology notes).

In all these cases, the O() notation hides terms that depend on the excluded graph H. for example, if H is a clique on k vertices, then G has at most O(nk\sqrt{log k}) edges.

So the question is: given a graph G, what's the smallest graph H that G excludes ? This problem is almost certainly NP-hard, and probably at least somewhat hard to approximate, but some approximation of the smallest graph (measured by edges or vertices) might be useful.

I was asked this question during our algorithms seminar a few days ago, and didn't have an answer.