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.
Contents |
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 <math>G = (V,E)</math>. <math>M \subseteq V</math> is a module of <math>G</math> if:
- the vertices of <math>M</math> cannot be distinguished by any vertex in <math>V \backslash M</math>, i.e.
<math>\forall u,v \in M, \forall x\in V \backslash M</math>, either <math>x</math> is adjacent to both <math>u</math> and <math>v</math> or <math>x</math> is not adjacent to both <math>u</math> and <math>v</math>.
- the vertices of <math>M</math> have the same set of outer neighbors, i.e.
<math>\forall u,v \in M, \{x \in V \backslash M</math> adjacent to <math>u\} =\{x \in V \backslash M</math> adjacent to <math>v\}</math>. <math>\emptyset</math>, <math>V</math> and all the singletons <math>\{v\}</math> for <math>v \in V</math> are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected components of a graph <math>G</math>, or of its complement graph are also modules of <math>G</math>. <math>M</math> is a strong module of a graph <math>G</math> if it does not overlap any other module of <math>G</math>: <math>\forall M'</math> module of <math>G</math>, either <math>M \cap M' = \emptyset</math> or <math>M \subseteq M'</math> or <math>M' \subseteq M</math>.
Modular decomposition tree
The strong modules of a graph <math>G</math> can be organized in a tree to represent their inclusion order, that is a module <math>M</math> will be an ancestor of another module in the tree if <math>M</math> contains this module. This tree is called the modular decomposition tree of <math>G</math>, its root is <math>V</math> and its leaves are the singletons <math>\{v\}</math>, for <math>v \in V</math>.
The modular decomposition theorem (Gallai 1967) shows that there are exactly three types of vertices in the modular decomposition tree. For each vertex <math>v_M</math> of the tree labeled by the module <math>M</math>, exactly one of the following conditions is true:
- the subgraph of <math>G</math> induced by <math>M</math>, <math>G[M]</math>, is not connected, then <math>v_M</math> is called a series node, and its children are the connected components of <math>G[M]</math>.
- the subgraph of the complement of <math>G</math> induced by <math>M</math>, <math>\overline{G}[M]</math>, is not connected, then <math>v_M</math> is called a parallel node, and its children are the connected components of <math>\overline{G}[M]</math>.
- both <math>G[M]</math> and <math>\overline{G}[M]</math> are connected, then <math>v_M</math> is called a prime node, and its children are labeled by the maximal strong modules included in <math>M</math>, which define a partition of <math>M</math>.
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, Tedder et al 2007).
References
- Gallai, Tibor (1967). "Transitiv orientierbare Graphen". Acta Mathematica Academiae Scientiarum Hungaricae 18: 25-66. doi:10.1007/BF02020961. MR0221974.
- 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.
- Papadopoulos, Charis; Voglis, Constantinos (2006). "Drawing graphs using modular decomposition". Lecture Notes in Computer Science 3842: 343-354. doi:10.1007/11618058_31. MR2229205.
- Tedder, Marc; Corneil, Derek; Habib, Michel; Paul, Christophe (2007), "Simple, Linear-time Modular Decomposition", Third Workshop on Graph Classes, Optimization, and Width Parameters, <http://arxiv.org/abs/0710.3901>.
