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).
What is the most important notion of sparsity for the design of efficient graph algorithms?
ds.algorithms;graph theory;graph algorithms;big picture