  In this paper, we revisit the split decomposition of graphs and give new
combinatorial and algorithmic results for the class of totally decomposable
graphs, also known as the distance hereditary graphs, and for two non-trivial
subclasses, namely the cographs and the 3-leaf power graphs. Precisely, we give
strutural and incremental characterizations, leading to optimal fully-dynamic
recognition algorithms for vertex and edge modifications, for each of these
classes. These results rely on a new framework to represent the split
decomposition, namely the graph-labelled trees, which also captures the modular
decomposition of graphs and thereby unify these two decompositions techniques.
The point of the paper is to use bijections between these graph classes and
trees whose nodes are labelled by cliques and stars. Doing so, we are also able
to derive an intersection model for distance hereditary graphs, which answers
an open problem.
