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(n2.376) algorithm for recognizing circular permutation graphs. Gardner gave an O(n2) 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).
