Modular decomposition

One of the basic concepts of graph theory is that of a module of a graph, which is a subset of the graph in which every element outside of the subset is either adjacent or non-adjacent to each member of the module. This generalizes the cotree consisting of connected components and their complements, as demonstrated by the graph below which is connected and so is its complement.



When a graph is a cograph, then it can be decomposed into atomic components by the modular decomposition. Otherwise, modules can occur that are unrelated to the connected components or their complements, in this case as Gallai showed the modular decomposition can be produced by the maximal modular subsets, which form a set partition of the component. This mechanism is used to produce the modular decomposition described below for the graph.



The first thing that one notices about this modular decomposition is that it is a laminar family. All the direct subsets of each module in the tree partition their parents. In fact, it is a nullfree laminar upper tree family. In this sense, the modular decomposition tree is like the parse tree of a graph.