Premium
Circular permutation graphs
Author(s) -
Rotem D.,
Urrutia J.
Publication year - 1982
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.3230120407
Subject(s) - permutation graph , combinatorics , mathematics , bit reversal permutation , vertex (graph theory) , discrete mathematics , cyclic permutation , permutation (music) , chordal graph , indifference graph , partial permutation , trapezoid graph , graph , 1 planar graph , symmetric group , physics , acoustics
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.