Syllabus
Disjoint Find Union (unions of equivalence classes starting from singletons) application on incremental connectivity (allowing edge insertions).
The same problem with backtracking.
Splay trees.
How to maintain topology of the forest using 'trees of paths'.
Application of 'trees of paths' - finding blocking flow in layered net in $O(m\log m)$ time.
Application of 'trees of paths' - maintaining bridge blocks or blocks.
Backtracking and maintainance of bridge blocks or blocks.
Clusterisation - maintainance of bridge blocks or blocks with arbitrary delete (worst case).
Sparsification - speeding up method for graph algorithms.
SPQR decomposition of plan(e/ar) graphs.
Top trees - edge oriented clusterisation. Tree representation with friendly user interface.
Application of Top trees on maintainance of bridge blocks and blocks in amortized polylog time, and other Top trees applications are left on TIN032.
Annotation
Amortized, randomized complexity. Dynamic structures representing graph, allowing fast queries for given basic graph properties
(connectivity, planarity) and fast updates of underlaying graph.