Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Proper Circular-Arc Graphs <s> Abstract : A graph G is a circular-arc graph if there is a 1-1 correspondence between the vertices of G and a family of arcs on a circle such that two distinct vertices are adjacent when the corresponding arcs intersect. Circular-arc graphs are characterized in terms of their adjacency matrix. (Author) <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Proper Circular-Arc Graphs <s> A proper circular-arc graph is a graph that has an intersection model formed by a family of overlapping arcs on some circle in which no arc contains another. A unit circular-arc graph is a graph that has an intersection model formed by a family of unit-length arcs on some circle. This paper gives structure theorems for proper circular-arc graphs and for unit circular-arc graphs. <s> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Proper Circular-Arc Graphs <s> A data structure called a PQ-tree is introduced. PQ-trees can be used to represent the permutations of a set U in which various subsets of U occur consecutively. Efficient algorithms are presented for manipulating PQ-trees. Algorithms using PQ-trees are then given which test for the consecutive ones property in matrices and for graph planarity. The consecutive ones test is extended to a test for interval graphs using a recently discovered fast recognition algorithm for chordal graphs. All of these algorithms require a number of steps linear in the size of their input. <s> BIB003
In this section, we survey some of the characterizations and recognition algorithms for PCA graphs. The first characterization of PCA graphs was described by Tucker BIB001 , based on the adjacency matrix of the graph. A characterization of PCA graphs by forbidden subgraphs has been also described by Tucker BIB002 , as below. For a graph G, denote by G * the graph obtained by adding an isolated vertex to G. The following concepts are relevant. Let A be a {0, 1}-matrix. Say that A has the consecutive 1's property on the columns, when there is a permutation of rows of A, such that the 1 entries become consecutive in the columns. More generally, A has the circular consecutive 1's property on the columns, when after a permutation of its rows the 1's or the 0's become consecutive in each column. Among other applications, the consecutive 1's property plays a key role in the recognition of interval graphs BIB003 , while the circular consecutive 1's property is employed in a characterization of P CA graphs BIB001 . Some characterizations and recognition algorithms for PCA graphs consider separately the PCA graphs which are co-bipartite, and the PCA graphs which are not. The following concept is useful for characterizing the latter class. The augmented adjacency matrix of a graph G is the one obtained from the adjacency matrix of G, by setting to 1 each entry of its main diagonal. Tucker characterized non co-bipartite PCA graphs, in terms of their augmented adjacency matrices.