On Comparability and Permutation Graphs

Abstract

This paper presents a technique for orienting a comparability graph transitively in $O(n^2 )$ time. The best previous algorithm for this problem required $\Omega (n^3 )$ time. When combined with a result in [SP], we can recognize permutation graphs in $O(n^2 )$ time, and determine in the same time complexity whether two permutation graphs are isomorphic. The orientation algorithm can also be used to reduce the problem of recognizing comparability graphs to that of recognizing transitive graphs. This gives an upper bound of $O(n^{2.49 + } )$ for comparability graph recognition, while the fastest previous algorithms required $\Omega (n^3 )$ time.