Modular decomposition
Recursively splitting a graph into subsets of nodes / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Modular decomposition?
Summarize this article for a 10 year old
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.
There are variants of modular decomposition for undirected graphs and directed graphs. For each undirected graph, this decomposition is unique.
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, for finding transitive orientations of comparability graphs, for optimization problems on graphs, and for graph drawing.