Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Helly Circular-Arc Graphs <s> Consider a finite family of non-empty sets. The intersection graph of this family is obtained by representing each set by a vertex, two vertices being connected by an edge if and only if the corresponding sets intersect. The intersection graph of a family of arcs on a circularly ordered set is called a circular-arc graph. In this paper we give a characterization of the circular-arc graph and we describe efficient algorithms for recognizing two subclasses. Also, we describe efficient algorithms for finding a maximum independent set, a minimum covering by cliques and a maximum clique of a circular-arc graph. <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Helly Circular-Arc Graphs <s> By making use of lexicographic breadth rst search (Lex-BFS) and partition renement with pivots, we obtain very simple algorithms for some well-known problems in graph theory. We give a O(n+mlogn) algorithm for transitive orientation of a comparability graph, and simple linear algorithms to recognize interval graphs, convex graphs, Y-semichordal graphs and matrices that have the consecutive ones property. Previous approaches to these problems used dicult preprocessing steps, such as computing PQ-trees or modular decomposition. The algorithms we give are easy to understand and straightforward to prove. They do not make use of sophisticated data structures, and the complexity analysis is straightforward. c 2000 Elsevier Science B.V. All rights reserved. <s> BIB002
We describe in this section results concerning the structure of HCA graphs. Recall that these graphs are exactly the CA graphs admitting a model whose arcs satisfy the Helly property. Such models are called HCA models. Among all the CA graphs, the HCA graphs are those closest to interval graphs. This is due precisely to the Helly property. Intervals of a line satisfy the Helly property, as already mentioned. Therefore, as for interval graphs, cliques of HCA graphs correspond to selected points of the circle. A consequence is that, like interval graphs, HCA graphs have at most n cliques. The first characterization of HCA has been given by Gavril BIB001 . It shows how HCA graphs arise from interval graphs, by extending the linear ordering of cliques to a circular ordering. Other characterizations of HCA graphs have been recently formulated, by Joeris, McConnell and Spinrad  and by Lin and Szwarcfiter  . Such characterizations are esentially similar, and were obtained independently. These results are presented below, under the notation of  . Before considering HCA graphs, the first aim is to characterize HCA models. Let M = (C, A) be a CA model. Recall that M = (C, A) denotes the complement model of M. The following theorem characterizes HCA models. Theorem 22 ([34,42] ): A CA model M is HCA if and only if (i) whenever three arcs of A cover C then two of them also cover C, and (ii) the intersection graph of M is chordal. Let M = (C, A) be a model which is not Helly. Say that M is minimally non Helly when removing any arc of A would turn the model Helly. Clearly, a minimally non Helly model has at least 3 arcs. The following is a characterization for such models. Next, we describe the characterization of HCA graphs. The following notation is employed. Let A be a CA model. An s-sequence of M is a maximal consecutive sequence of start points, in the circular ordering. Similarly, define a t-sequence, for the end points. In general, an extreme sequence is an s-sequence or a t-sequence. Clearly, the extreme sequences are a partition of the extreme points, and are circularly ordered. Let S be a extreme sequence. Denote by NEXT (S) and NEXT −1 (S), respectively the extreme sequences that immediately preceed S and suceed S, in the ordering. Also, if p is an arbitrary extreme point of C then SEQUENCE(p) denotes the unique extreme sequence that contains p. The following definitions are central. Let s i be a start point of M, and S = SEQUENCE(s i ). Say that s i is stable precisely when i = j or A i ∩ A j = ∅, for every t j ∈ NEXT −1 (S). More generally, the model M is stable when all starting points are so. Figure 8 illustrates two CA models of a triangle. The first of them is not stable, but the second is so. Next, we describe a family of graphs. It will be shown that these graphs form a forbidden family for HCA graphs. An obstacle is a graph H, containing a complete set Q ⊆ V (H), |Q| = q ≥ 3, admitting a circular ordering v 1 , . . . , v q of its vertices, where each edge v i , v i+1 satisfies (ii): In Next, we consider the algorithms that arise from the described characterizations. Gavril's characterization leads directly to a simple algorithm for recognizing HCA graphs. Let G be a graph. Construct the clique matrix of G and verify if its columns satisfy the circular consecutive 1's property. By Theorem 21, G is a HCA graph precisely when the answer is positive. An HCA graph has at most n cliques. We can therefore restrict to clique matrices having at most n cliques, otherwise G is not HCA. Using the algorithm by Paull and Unger  , we can generate these O(n) cliques in O(n 3 ) time. Checking the circular consecutive 1's property can be done in linear time. Consequently, the complexity of algorithm BIB001 is O(n 3 ). Finally, consider the algorithms based on the characterizations of   . For recognizing minimally non Helly models, apply Corollary 3. There is no difficulty to verify conditions (i) and (ii) in O(n) time, given the model. For recognizing HCA models, the basis is Theorem 22. A direct implementation of it would consist of verifying whether the intersection graph G c of M is chordal. This would lead to an algorithm of complexity O(n 2 ), because G c has O(n 2 ) edges. However checking co-chordality of G c , instead of chordality of G c , can be done in O(m) time, because G c has at most m edges, and verifying co-chordality can be done in linear time BIB002 . Consequently, HCA models can be recognized in O(m) time. However, Joeris, McConnell and Spinrad  describe more elaborate implementations, employing union-find tools, which requires just O(n) time. The algorithm for recognizing HCA graphs   follows from Theorem 23. Its outline is as follows. Let G be a graph. 