I just put up another preprint, "Densities of Minor-Closed Graph Families", as arXiv:1009.5633.

It's pretty well known that planar graphs have at most \( 3n-6 \) edges, outerplanar graphs have at most \( 2n-3 \) edges, linklessly embeddable graphs have at most \( 4n-10 \) edges, etc. Simplifying these formulas by dividing by \( n \) and ignoring lower order terms, we can say that the planar graphs have density \( 3 \), outerplanar graphs have density \( 2 \), and linkless graphs have density \( 4 \).

But fractional densities are also possible. Matchings have density \( 1/2 \), the graphs in which each component is a path with at most two edges have density \( 2/3 \), and in the same way one can find minor-closed families whose densities are \( 3/4, 4/5, 5/6, 6/7, \dots \) And of course the number 1 itself is a density of a minor-closed family, for instance it is the density of the forests, or of the graphs in which each component has at most three vertices. But beyond that it gets more complicated: the next few numbers that can be densities of minor-closed families are \( 6/5, 5/4, 9/7, 4/3, 15/11, 11/8, \dots \)

This paper examines the structure of this set \( \{1/2, 2/3, 3/4, \dots 1, 6/5, 5/4, 9/7, \dots \} \) of densities. It turns out to be well-ordered (it can approach a limit point from below but not from above) and topologically closed; if \( x \) belongs to this set, then \( x+1 \) not only belongs to it but is a limit point of points in this set. So \( 1 \) is a limit point of the numbers \( 1/2, 2/3, 3/4, \dots \) but then the numbers \( 3/2, 5/3, 7/4, \dots \) are each themselves limit points, and \( 2 \) is a limit point of these limit points. Similarly \( 3 \) is a limit point of limit points of limit points. For this reason, the order type of the set of densities is at least \( \omega^\omega \), but I don't know whether that's its exact order-theoretic description or whether it could be an even larger ordinal. (Incidentally, this is why I asked this MathOverflow question last May.) I also don't even know whether the set of densities contains any irrational numbers.

There are no algorithms in the paper, but I used a couple of tricks coming from graph algorithms (primarily separator theorems and color-coding) to show that every minor-closed family contains graphs that are close to the maximum density and have a very repetitive structure, which I needed in order to prove these results.