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 (such as computing graph cutes). Unfortunately in general computing a tree width decomposition is np hard 

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


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