It would be nice if there were an article on using various graph decompositions. For example, it is very frequently useful to decompose a graph into one or more of the following:
- connected components (or strongly connected components if dealing with directed graphs), though this is so frequently used it's almost trivial
- 2-connected components
- a tree decomposition (a la treewidth)
- a clique decomposition (a la clique width)
- some sort of product of other graphs (Cartesian product is particularly nice because it satisfies unique factorization)
- others?
I am not experienced enough to write such an article, but thought I'd throw the idea out there.
[Already posted as a comment under the "Structural Graph Theory" stub, but reposted here as it seems appropriate.]
Post new comment
(Note: commenting is not possible on this snapshot.)