Machine Learning, etc: Computationally nice structures

One approach to solving hard problems is to break them into computationally efficient parts. 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. 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.