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 for details.

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 for details.