On testing isomorphism of permutation graphs

Research output: Contribution to journalArticlepeer-review

56 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)13-21
Number of pages9
Issue number1
StatePublished - Jan 1 1981
Externally publishedYes

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'On testing isomorphism of permutation graphs'. Together they form a unique fingerprint.

Cite this