Graph Theory37 sections · 1633 units
Open in Course

Decomposition Tree vs Original Tree

(Two different structures)

The original tree has edges connecting nodes physically. The decomposition tree has edges connecting centroids based on removal order. These represent different relationships. A node's parent in the decomposition tree is the centroid that removed it. A node's children in the decomposition tree are centroids of components created by removing it.

These relationships do not match the original edges. These are different relationships. A node far away in the original tree might be close in the decomposition tree. This is useful for distance queries.