Circular permutation graphs

A new class of intersection graphs called circular permutation graphs is introduced and characterized. A circular permutation diagram for a permutation P (1),…, P ( n ) consists of two circles C 1 and C 2 ; the numbers 1′, 2′,…,n′ and P (1),…, P ( n ) on C 1 and C 2 , respectively; and a set of n chords 1, 2,…, n connecting i to i ′ such that two chords intersect each other at most once. A graph G represents a circular permutation diagram if there is a labeling of V ( G ) with {1,…, n} such that i is adjacement to j iff i and j intersect. Graphs which represent at least one permutation diagram are called circular permutation graphs. Circular permutation graphs generalize permutation graphs [2], [8] and are embedded in the set of comparability graphs [4]. The characterization leads to a recognition algorithm which requires O (δ|E|) steps where δ is the maximum degree of a vertex.