Are there good implementations for easy subclasses of NP-hard graph problems
I'd be surprised if there existed a graph library recognizing them all (there is a lot of them), but most of the algorithms you will find in the litterature are focused on a very small amount of classes... For example chordal graphs (easy to recognise), or treewidth-bounded graphs (much harder.. hopefully the algorithms given for these classes are almost useless in practice), planar graphs, ...

In Sage (http://www.sagemath.org/), we are trying to build a large graph library, with recognition algorithms and methods to solve NP-Hard problems. For instance, we have the following methods :

g.is_bipartite
g.is_chordal
g.is_circular_planar
g.is_clique
g.is_drawn_free_of_edge_crossings
g.is_equitable
g.is_eulerian
g.is_even_hole_free
g.is_forest
g.is_gallai_tree
g.is_hamiltonian
g.is_interval
g.is_line_graph
g.is_odd_hole_free
g.is_overfull
g.is_perfect
g.is_planar
g.is_prime
g.is_regular
g.is_split
g.is_transitively_reduced
g.is_tree
g.is_triangle_free
g.is_vertex_transitive


The best is probably to read the (unfortunately) long list of methods related to graphs...

http://www.sagemath.org/doc/reference/graphs.html

(I wrote a short tutorial there : http://www-sop.inria.fr/members/Nathann.Cohen/tut/Graphs/ )

Nathann