I think you might want to look at the related/(same?) concept of treewidth. Its a much stronger sparseness requirement than constant degree, planar, etc, and if you have something like  $\mathcal O(\log n)$ tree width, many NP-Hard problems on graphs become easy.

See the wikipedia [page][1] for details.


  [1]: http://en.wikipedia.org/wiki/Tree_decomposition