Approximation algorithms for Maximum Independent Set on special classes of graphs
There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: see this entry in the graph classes website.