the subgraphs induced by modules. The modules of a graph are therefore of great algorithmic interest. A set of nested modules, of which the modular decomposition is an example, can be used to guide the recursive solution of many combinatorial problems on graphs, such as recognizing and transitively orienting comparability graphs, recognizing and finding permutation representations of permutation graphs, recognizing whether a graph is a cograph and finding a certificate of the answer to the question, recognizing interval graphs and finding interval representations for them, defining distance-hereditary graphs (Spinrad, 2003) and for graph drawing (Papadopoulos, 2006). They play an important role in Lovász's celebrated proof of the perfect graph theorem (Golumbic, 1980). For recognizing distance-hereditary graphs and circle graphs, a further generalization of modular decomposition, called the split decomposition, is especially useful (Spinrad, 2003). To avoid the possibility of ambiguity in the above definitions, we give the following formal definitions of modules. . is a module of if: the vertices of cannot be distinguished by any vertex in , i.e., , either is adjacent to both and or is neither adjacent to nor to . the vertices of have the same set of outer neighbors, i.e., . , and all the singletons for are modules, and are called trivial modules. A graph is prime if all its modules are trivial. Connected components of a graph , or of its complement graph are also modules of . is a strong module of a graph if it does not overlap any other module of : module of , either or or . Modular quotients and factors If and are disjoint modules, then it is easy to see that either every member of is a neighbor of every element of , or no member of is adjacent to any member of . Thus, the relationship between two disjoint modules is either adjacent or nonadjacent. No relationship intermediate between these two extremes can exist. Because of this, modular partitions of where each partition class is a module are of particular interest. Suppose is a modular partition. Since the partition classes are disjoint, their adjacencies constitute a new graph, a quotient graph , whose vertices are the members of . That is, each vertex of is a module of G, and the adjacencies of these modules are the edges of . In the figure below, vertex 1, vertices 2 through 4, vertex 5, vertices 6