An \(O(n^ 2)\) incremental algorithm for modular decomposition of graphs and 2-structures (Q1897475)

A module of a graph is a set of vertices that is indistinguishable from outside. I.e., every vertex outside a module is either adjacent to all vertices in the module, or is adjacent to no vertex of the module. This concept generalizes to 2-structures, which are complete graphs with an equivalence relation on the edges. The modular decomposition of a graph or 2-structure is a tree, namely the transitive reduction of the containment relation on the set of all modules. The cotree of a cograph [\textit{D. G. Corneil}, \textit{Y. Perl} and \textit{L. K. Stewart}, SIAM J. Comput. 14, 926-934 (1985; Zbl 0575.68065)] is a special form of such a decomposition tree. The modular decomposition is a linear space representation of a graph which supports efficient algorithms for problems like recognition of comparability graphs and permutation graphs. Another incremental \(O(n^2)\) algorithm computing the modular decomposition of graphs is known [\textit{J. H. Muller} and \textit{J. Spinrad}, J. Assoc. Comput. Mach. 36, No. 1, 1-19 (1989; Zbl 0671.68030)], and there are also linear time algorithms for this problem [\textit{A. Cournier} and \textit{M. Habib}, Lect. Notes Comput. Sci. 657, 212- 224 (1993)].