Graph classes between parity and distance-hereditary graphs

Several graph problems (e.g., steiner tree, connected domination, hamiltonian path, and isomorphism problem), which can be solved in polynomial time for distance-hereditary graphs, are NP-complete or have unknown complexity for parity graphs. Moreover, the metric characterizations of these two graph classes suggest an excessive gap between them. We introduce a family of classes forming an infinite lattice with respect to inclusion, whose extreme points are exactly parity and distance-hereditary classes. Then, we characterize these classes using Cunningham decomposition and use such a characterization in order to show efficient algorithms for the recognition and isomorphism problems.