Modular decomposition
From Wikipedia, the free encyclopedia
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.
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.
[edit] 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.
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 .
[edit] 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 vM of the tree labeled by the module M, exactly one of the following conditions is true:
- the subgraph of G induced by M, G[M], is not connected, then vM 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 vM is called a parallel node, and its children are the connected components of .
- both G[M] and are connected, then vM 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.
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).
[edit] 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.
- James, L.O.; Stanton, R.G.; Cowan, D.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.