modular decomposition tree should support the operation that inputs a node and returns the set of vertices of that the node represents. An obvious way to do this is to assign to each node a list of the vertices of that it represents. Given a pointer to a node, this structure could return the set of vertices of that it represents in time. However, this data structure would require space in the worst case. An -space alternative that matches this performance is obtained by representing the modular decomposition tree using any standard rooted-tree data structure and labeling each leaf with the vertex of that it represents. The set represented by an internal node is given by the set of labels of its leaf descendants. It is well known that any rooted tree with leaves has at most internal nodes. One can use a depth-first search starting at to report the labels of leaf-descendants of in time. Each node is a set of vertices of and, if is an internal node, the set of children of is a partition of where each partition class is a module. They therefore induce the quotient in . The vertices of this quotient are the elements of , so can be represented by installing edges among the children of . If and are two members of and and , then and are adjacent in if and only if and are adjacent in this quotient. For any pair of vertices of , this is determined by the quotient at children of the least common ancestor of and in the modular decomposition tree. Therefore, the modular decomposition, labeled in this way with quotients, gives a complete representation of . Many combinatorial problems can be solved on by solving the problem separately on each of these quotients. For example, is a comparability graph if and only if each of these quotients is a comparability graph (Gallai, 67; Möhring, 85). Therefore, to find whether a graph is a comparability graph, one need only find whether each of the quotients is. In fact, to find a transitive orientation of a comparability graph, it suffices to transitively orient each of these quotients of its modular decomposition (Gallai, 67; Möhring, 85). A similar phenomenon applies for permutation graphs, (McConnell and Spinrad '94), interval graphs (Hsu and Ma '99), perfect graphs, and other graph classes. Some important combinatorial optimization problems on graphs can