A dynamic algorithm for maintaining the modular decomposition of a graph

The modular decomposition of a graph is a useful structure that can be computed in O(m+n) time. We will review its basic properties and then present an algorithm that maintains the modular decomposition of a _cograph_ in O(n) time per edge insertion or deletion. We will briefly discuss extending the algorithm to all graphs.