For instance, Globerson/Jaakkola do approximate counting by decomposing graph into planar graphs. In each part, the problem reduces to perfect matchings which can be solved efficiently on planar graph. Bouchet/Jordan decompose counting bipartite perfect matchings into much easier problems that count matchings perfect on "one side" of the graph. Sontag/Jaakola solve subproblems on star-shaped subgraphs of original graph, the symmetry of star graph enabling a very fast solution to each subproblem.
I recently came across graph class database which gives information on thousands of graph classes. It shows dozens (hundreds?) distinct tractable classes for exact maximum independent set, and most of them seem to have unbounded tree width. I haven't heard of most of those classes and would be curious to know how many distinctly interesting algorithms they correspond to
Here are a few computationally nice structures I've seen employed in Machine Learning and Vision literature
Upper-bounded tree width
Everything is easy via tree decomposition
Almost everything is easy via loopy belief propagation
Easy minimization of submodular functions. Easy counting of certain structures by reduction to perfect matchings.
Easy counting of unweighted local structures
Easy MAP inference with NAND potentials
Very efficient updates for MAP inference
A generalization of line graphs. Easy maximum independent set, and counting by reduction to matchings
Any other useful classes I missed?