Weakly triangulated comparability graphs

The class of weakly triangulated comparability graphs and their complements are generalizations of interval graphs and chordal comparability graphs. W e show that problems on these classes of graphs can be solved efficiently b y transforming them into problems on chordal bipartite graphs. We show that recognition and independent set on weakly triangulated comparability graph s can be solved in O(n(2)) time in this manner, and that the number of weak ly triangulated comparability graphs is 2(Theta(nlog2n)). We also give algo rithms to compute transitive closure and transitive reduction in O(n(2)logl ogn) time if the underlying undirected graph of the transitive closure is a weakly triangulated comparability graph.