What is the most important notion of sparsity for the design of efficient graph algorithms?
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.