Graph decompositions and factorizing permutations

A factorizing permutation of a given graph is simply a permutation of its vertices of which all decomposition sets are factors [3]. Such a concept appears to play a central role in recent papers dealing with graph decomposition. It is applied here for modular decomposition of directed graphs, and we propose a simple linear algorithm that computes the whole decomposition tree when a factorizing permutation is provided. The approach of using parenthesized factors of a list was first used by Hopcroft and Tarjan for triconnected components search [14]. Our algorithm can be seen as a common generalization of Hsu and Ma [16, 15] for modular decomposition of chordal graphs and Habib, Huchard and Spinrad [10] for inheritance graphs decomposition [1]. It also suggests many new decomposition algorithms for various notions of graph decompositions