Modular decomposition

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.As the notion of modules has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, intervals, and partitive sets. Perhaps the earliest reference to them, and the first description of modular quotients and the graph decomposition they give rise to appeared in (Gallai 1967).If X {displaystyle X}   and Y {displaystyle Y}   are disjoint modules, then it is easy to see that either every member of X {displaystyle X}   is a neighbor of every element of Y {displaystyle Y}  , or no member of X {displaystyle X}   is adjacent to any member of Y {displaystyle Y}  . Thus, the relationship between two disjoint modules is either adjacent or nonadjacent. No relationship intermediate between these two extremes can exist.Fortunately, there exists such a recursive decomposition of a graph that implicitly represents all ways of decomposing it; this is the modular decomposition. It is itself a way of decomposing a graph recursively into quotients, but it subsumes all others. The decomposition depicted in the figure below is this special decomposition for the given graph.A data structure for representing the modular decomposition tree should support the operation that inputs a node and returns the set of vertices of G {displaystyle G}   that the node represents. An obvious way to do this is to assign to each node a list of the k {displaystyle k}   vertices of G {displaystyle G}   that it represents. Given a pointer to a node, this structure could return the set of vertices of G {displaystyle G}   that it represents in O ( k ) {displaystyle {mathcal {O}}(k)}   time. However, this data structure would require Θ ( n 2 ) {displaystyle Theta (n^{2})}   space in the worst case. Modular decomposition of directed graphs can be done in linear time (McConnell & de Montgolfier 2005).