Linear-time modular decomposition and efficient transitive orientation of comparability graphs

Abstract

A module of an undirected graph is a set X of nodes such for each node x not in X, either every member of X is adjacent to x , or no member of X is adjacent to x. There is a canonical linear-space representation for the modules of a graph, called the modular decomposition. The modular decomposition facilitates solution of a number of combinatorial problems on certain classes of graphs, and algorithms for computing it have a lengthy history. Closely related to modular decomposition is the transitive orientation problem, which is the problem of assigning a direction to each edge of a graph so that the resulting digraph is transitive, if such an assignment is possible. We give the lirst linear-time algorithm for modular decomposition, and a new bound of 0 (ri +m logn) on transitive orientation and the problem of recognizing permutation graphs and two-dimensional partial orders.