Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 8 ([26] <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> Theorem 8 ([26] <s> Given a set F of digraphs, we say a graph G is a F-graph (resp., F*-graph) if it has an orientation (resp., acyclic orientation) that has no induced subdigraphs isomorphic to any of the digraphs in F. It is proved that all the classes of graphs mentioned in the title are F-graphs or F*-graphs for subsets F of a set of three digraphs. <s> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 8 ([26] <s> We introduce a simple new technique which allows us to solve several problems that can be formulated as seeking a suitable orientation of a given undirected graph. In particular, we use this technique to recognize and transitively orient comparability graphs, to recognize and represent proper circular arc graphs, and to recognize and represent proper interval graphs. As a consequence, we derive and represent proper interval graphs. As a consequence, we derive simple new proofs of a theorem of Ghouila-Houri and a theorem of Skrien. Our algorithms are conceptually simpler than (and often of comparable efficiency to) the existing algorithms for these problems. © 1995 John Wiley & Sons, Inc. <s> BIB003 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 8 ([26] <s> Our main result is a linear-time (that is, time $O(m+n)$) algorithm to recognize and represent proper circular-arc graphs. The best previous algorithm, due to A. Tucker, has time complexity $O(n^2)$. We take advantage of the fact that (among connected graphs) proper circular-arc graphs are precisely the graphs orientable as local tournaments, and we use a new characterization of local tournaments. The algorithm depends on repeated representation of portions of the input graph as proper interval graphs. Thus we also find it useful to give a new linear-time algorithm to represent proper interval graphs. This latter algorithm also depends on an orientation characterization of proper interval graphs. It is conceptually simple and does not use complex data structures. As a byproduct of the correctness proof of the algorithm, we also obtain a new proof of a characterization of proper interval graphs by forbidden subgraphs. <s> BIB004
): Let G be a co-bipartite graph. Then G is a PCA graph if and only if G is a proper interval bigraph. The following are key concepts for a characterization of PCA graphs, introduced by Hell, Bang-Jensen and Huang  , Huang   and Skrien BIB002 . They generalize tournaments, that is, orientations of a complete graph. A graph G is a local tournament when G admits an orientation, such that A round enumeration of a digraph D is a circular ordering v 1 , . . . , v n of its vertices, such that for each v i there are integers r and s, such that Finally, say that G is round when it admits an orientation having a round enumeration. In the special case that v 1 , . . . , v n is a linear ordering, instead of a circular ordering, then v 1 , . . . , v n is a straight enumeration and G is called straight. The latter concept has been employed in the following characterization of proper interval graphs. The above Theorem has been generalized to a characterization of PCA graphs, as follows. Theorem 10 ( BIB004 BIB002 ): The following statements are equivalent for a connected graph G. As for the recognition problem, the first algorithm for recognizing PCA graphs is by Tucker BIB001 , following his matrix characterization of this class. The algorithm has complexity O(n 2 ). This complexity is achieved by applying a linear time algorithm for checking the circular consecutive 1's property of the augmented adjacency matrix of G, c.f.  . Such a linear time algorithm can be obtained by employing PQ trees. An algorithm for recognizing PCA graphs based on orientations has been described by Hell and Huang BIB003 . Its complexity is O(∆m), where ∆ is the maximum degree of the graph. The first linear time recognition algorithm is by Deng, Hell and Huang BIB004 . The following concepts are useful for describing this algorithm. Let G be a graph. A block of G is a maximal set of pairwise twins. The reduced graph G R of G is the graph obtained from G by identifying each subset of vertices formed by pairwise twins. A mixed graph is a graph in which possibly some edges are oriented and some are not. A straight mixed orientation of G is a mixed graph, in which the oriented edges form a straight orientation of the reduced graph G R of G. Let S 1 , S 2 be mixed orientations of subgraphs of G. Then S 1 , S 2 are consistent when the edges of G which are directed in both S 1 , S 2 , are directed in the same way in these two orientations. The following lemma is employed in the algorithm.