Permutation Graphs and Transitive Graphs
Shimon Even, Amir Pnueli, Abraham Lempel · Journal of the ACM · 1972
A graph G with vertex set N = {1, 2, .-. , n} is called a permutation graph there exists a permutation P on N such that for i,j E N, (i -j)[P-'(i) -P-'(j)] < 0 if ar only if i and j are joined by an edge in G.A structural relationship is established between permutation graphs and transitive graph An algorithm for determining whether a given graph is a permutation graph is given.Efficie, algorithms for finding a maximum size clique and a minimum coloration of transitive grapl are presented.These algorithms are then shown to be applicable in solving problems in memo] allocation and circuit layout.