\(P_ 4\)-trees and substitution decomposition (Q1201812)

Cotrees for cographs (\(P_ 4\)-free graphs) are generalized to \(P_ 4\)- trees, which can be used to give the modular decomposition of the graph. A vertex addition algorithm is given to construct the \(P_ 4\)-tree of an \(n\)-vertex \(m\)-edge graph in \(O(n+m)\) time. A second algorithm is then given to produce the modular decomposition of the graph in almost linear time. A very clear summary of the applications of modular decomposition is included.