Premium
A linear time algorithm to recognize circular permutation graphs
Author(s) -
Sritharan R.
Publication year - 1996
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/(sici)1097-0037(199605)27:3<171::aid-net1>3.0.co;2-f
Subject(s) - combinatorics , permutation graph , mathematics , chordal graph , intersection graph , discrete mathematics , algorithm , graph , line graph
An undirected graph G is a circular permutation graph if it can be represented by the following intersection model: Each vertex of G corresponds to a chord in the annular region between two concentric circles, and two vertices are adjacent in G if and only if their corresponding chords intersect each other exactly once. Circular permutation graphs are a generalization of permutation graphs. Rotem and Urrutia introduced and characterized this class of graphs and their characterization yields an O ( n 2.376 ) algorithm for recognizing circular permutation graphs. Gardner gave an O ( n 2 ) recognition algorithm. We provide an alternate characterization and show that an O ( m + n ) recognition algorithm can be derived from the new characterization. Our algorithm also constructs the intersection model when the input graph is a circular permutation graph (CPG). © 1996 John Wiley & Sons, Inc.