Abstract
Split decomposition of graphs was introduced by Cunningham (under the name join decomposition) as a generalization of the modular decomposition. This paper undertakes an investigation into the algorithmic properties of split decompo- sition. We do so in the context of graph-labelled trees (GLTs), a new combinatorial object designed to simplify its consideration. GLTs are used to derive an incremental characterization of split decomposition, with a simple combinatorial description, and to explore its properties with respect to Lexicographic Breadth-First Search (LBFS). Applying the incremental characterization to an LBFS ordering results in a split de- composition algorithm that runs in time O(n + m)α(n + m), where α is the inverse Ackermann function, whose value is smaller than 4 for any practical graph. Com- pared to Dahlhaus' linear time split decomposition algorithm (Dahlhaus in J. Algo- rithms 36(2):205-240, 2000), which does not rely on an incremental construction, our algorithm is just as fast in all but the asymptotic sense and full implementation