The density of a sparse family of graphs is defined as the
supremum of the ratio of the number of edges to the number of vertices
over graphs in the family. For example, the density of forests is one,
and the density of planar graphs is three. Eppstein has recently
initiated a systematic study of the set of possible densities of
minor-closed graph families. We answer one of his questions, showing
that all such densities are rational.
Based on joint work with Rohan Kapadia.
The ACO Seminar (2014–2015)