Graph classes between parity and distance-hereditary graphs

Several graph problems (e.g., steiner tree, connected domination, hamiltonian path, and iso- morphism problem), which can be solved in polynomial time for distance-hereditary graphs, are NP-complete or open 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 innite lattice with respect to inclusion, whose bottom and top elements are the class of the distance-hereditary graphs and the class of the parity graphs, respectively. We propose this family as a reference framework for studying the computational complexity of fundamental graph prob- lems. For this purpose we characterize these classes using Cunningham decomposition and then use the devised structural characterization in order to show ecient algorithms for the recogni- tion and isomorphism problems. As far as the isomorphism graph problem is concerned we nd ecient algorithms for an innite number of dierent classes (forming a chain with respect to the inclusion relation) in the family.