What is the most important notion of sparsity for the design of efficient graph algorithms? There are several competing notions of a "sparse graph".  For instance, a surface-embeddable graph could be considered sparse.  Or a graph with bounded edge density.  Or a graph with high girth.  A graph with large expansion.  A graph with bounded treewidth.  (Even within the subfield of random graphs, it is slightly ambiguous as to what could be called sparse.)  Et cetera.

What notion of "sparse graph" has had the most impact on the design of efficient graph algorithms, and why?  Similarly, what notion of "dense graph" ... ?  (NB: Karpinski has worked a great deal on approximation results for one standard model of dense graphs.)

I have just seen a talk by J. Nesetril on a program of his (together with P. Ossona de Mendez) to capture measures of sparsity in graphs within a unified (asymptotic) framework.  My question -- yes, maybe quite subjective and I expect different camps -- is motivated by the desire to catch a multi-faceted perspective on the use of sparsity in algorithms (and plug any gaps in my own understanding of the issue).
I think that by any reasonable standard an n &times; n &times; n three-dimensional grid graph would have to be considered sparse, and that rules out most candidate definitions involving surface embeddings or minors. (Sublinear treewidth would still be possible, though.)

My current favorite sparsity measure is degeneracy. The degeneracy of a graph is the minimum, over all linear orderings of the vertices of the graph, of the maximum outdegree in the directed acyclic orientation of the graph formed by orienting each edge from earlier to later vertices in the ordering. Equivalently, it's the maximum, over all subgraphs, of the minimum degree in the subgraph. So for instance planar graphs have degeneracy five because any subgraph of a planar graph has a vertex of degree at most five. Degeneracy is easy to calculate in linear time, and the linear ordering that comes from the definition is useful in algorithms.

Degeneracy is within a constant factor of some other standard measures including arboricity, thickness, and the maximum average degree of any subgraph, but those are I think harder to use.