A LINEAR-TIME ALGORITHM TO RECOGNIZE CIRCULAR PERMUTATION GRAPHS

An undirected graph G is a circular permutation graph if it can be rep resented by the following intersection model: Each vertex of G corresp onds 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 introduc ed and characterized this class of graphs and their characterization y ields an O(n(2376)) algorithm for recognizing circular permutation gra phs. Gardner gave an O(n(2)) recognition algorithm. We provide an alte rnate characterization and show that an O(m + n) recognition algorithm can be derived from the new characterization. Our algorithm also cons tructs the intersection model when the input graph is a circular permu tation graph (CPG). (C) 1996 John Wiley & Sons, Inc.