Premium
On testing isomorphism of permutation graphs
Author(s) -
Colbourn Charles J.
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110103
Subject(s) - graph isomorphism , combinatorics , mathematics , permutation graph , isomorphism (crystallography) , discrete mathematics , chordal graph , comparability , induced subgraph isomorphism problem , graph , line graph , voltage graph , crystallography , chemistry , crystal structure
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.