2008/10/10 by Emeric Gioan, Gioan, Emeric, Christophe Paul +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #G.2.1 #G.2.2 #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #cs.DM #cs.DS
paper · pdf · doi:10.48550/arxiv.0810.1823
extended abstract appeared in ISAAC 2007: Dynamic distance hereditary graphs using split decompositon. In International Symposium on Algorithms and Computation - ISAAC. Number 4835 in Lecture Notes, pages 41-51, 2007
openalex publication_date 2008/10/10 · arxiv created 2011/04/18 · arxiv updated 2011/04/19 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
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.