In graph theory, modular decomposition is the mapping of an undirected graph into a tree with three types of vertices, labeled by subsets of vertices of the graph called modules. graph theory. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ...

This notion can be generalized to other structures (for example directed graphs) and is useful to design efficient algorithms for the recognition of some graph classes, transitive orientation, optimization problems, or graph drawing. In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ... As a branch of Graph theory, Graph drawing applies topology and geometry to derive visual and haptic representations of graphs. ...

Modules

As the notion of modular decomposition has been rediscovered in many areas, modules have also been called autonomous sets, homogeneous sets, intervals, partitive sets, etc.

We give two equivalent definitions of a module in an undirected graph G = (V,E). is a module of G if:

• the vertices of M cannot be distinguished by any vertex in , i.e.

, either x is adjacent to both u and v or x is not adjacent to both u and v.

• the vertices of M have the same set of outer neighbors, i.e.

adjacent to adjacent to v}.

, V and all the singletons {v} for are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected components of a graph G, or of its complement graph are also modules of G. In mathematics, a singleton is a set with exactly one element. ... In an undirected graph, a connected component or component is a maximal connected subgraph. ... In graph theory the complement or inverse of a graph is a graph on the same vertices such that two vertices of are adjacent if and only if they are not adjacent in . ...

M is a strong module of a graph G if it does not overlap any other module of G: module of G, either or or .

Modular decomposition tree

The strong modules of a graph G can be organized in a tree to represent their inclusion order, that is a module M will be an ancestor of another module in the tree if M contains this module. This tree is called the modular decomposition tree of G, its root is V and its leaves are the singletons {v}, for .

The modular decomposition theorem (Gallai 1967) shows that there are exactly three types of vertices in the modular decomposition tree. For each vertex v_M of the tree labeled by the module M, exactly one of the following conditions is true: Tibor Gallai (1912–1992) was a Hungarian mathematician. ...

• the subgraph of G induced by M, G[M], is not connected, then v_M is called a series node, and its children are the connected components of G[M].
• the subgraph of the complement of G induced by M, , is not connected, then v_M is called a parallel node, and its children are the connected components of .
• both G[M] and are connected, then v_M is called a prime node, and its children are labeled by the maximal strong modules included in M, which define a partition of M.

Cographs are the graphs that only have parallel or series nodes in their modular decomposition tree. Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... In mathematics and computer science, graph theory studies the properties of graphs. ... A tree structure is a way of representing the hierarchical nature of a structure in a graphical form. ... Graph theory is a growth area in mathematical research, and has a large specialized vocabulary. ... A partition of U into 6 blocks: a Venn diagram representation. ... In graph theory, a cograph, or P4-free graph, is a graph that fulfills the following equivalent properties: Can be constructed from isolated vertices by complement, joint union and disjoint union. ...

The first polynomial algorithm to compute the modular decomposition tree of a graph was published in 1972 (James, Stanton & Cowan 1972) and now linear algorithms are available (McConnell & Spinrad 1999, Habib, Montgolfier & Paul 2004).

References

• Gallai, Tibor (1967). "Transitiv orientierbare Graphen". Acta Mathematica Academiae Scientiarum Hungaricae 18: 25-66. DOI:10.1007/BF02020961. MR0221974. 

• Habib, Michel; de Montgolfier, Fabien; Paul, Christophe (2004). "A simple linear-time modular decomposition algorithm for graphs, using order extension". Lecture Notes in Computer Science 3111: 187-198. DOI:10.1007/b98413. MR2159531. 

• Papadopoulos, Charis; Voglis, Constantinos (2006). "Drawing graphs using modular decomposition". Lecture Notes in Computer Science 3842: 343-354. DOI:10.1007/11618058_31. MR2229205. 

• James, Lee O.; Stanton, Ralph G.; Cowan, Donald .D (1972). "Graph decomposition for undirected graphs". Proceedings of the third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (CGTC'72): 281-290. MR0351909. 

• McConnell, Ross M.; Spinrad, Jeremy P. (1999). "Modular decomposition and transitive orientation". Discrete Mathematics 201: 189-241. DOI:10.1016/S0012-365X(98)00319-7. MR1687819.