On testing isomorphism of permutation graphs
Charles J. Colbourn · Networks · 1981
Abstract A polynomial time algorithm for testing isomorphism of permutation graphs (comparability graphs of 2‐dimensional partial orders) is described. It operates by performing two types of simplifying transformations on the graph; the contraction of duplicate vertices and the contraction of uniquely orientable induced subgraphs.