Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> General Circular-Arc Graphs <s> An undirected graph G is called a circular-arc graph if there exists a family of arcs on a circle and a 1–1 correspondence between vertices and arcs such that two distinct vertices are adjacent if and only if the corresponding arcs overlap. Such a family is called a circular-arc model for G. In this paper we present an $O(n)^3 $-step algorithm for testing whether an n-vertex graph is a circular-arc graph, and if it is, constructing a circular-arc model. Unfortunately the algorithm, its proof, and its efficient implementation are all quite involved. <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> General Circular-Arc Graphs <s> Abstract This paper shows that the recognition problem on circular-arc graphs which can be partitioned into two cliques is reducible to the recognition problem on two-dimensional partial orders. This can be used to simplify the recognition algorithm for circular-arc graphs devised by Tucker. <s> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> General Circular-Arc Graphs <s> Circular-arc graphs have a rich combinatorial structure and it has been suggested that this is why complicated ad hoc methods, instead of general principles, are the basis of almost all results in the theory of circular-arc graphs. We establish a relationship between circular-arc graphs and chordal bipartite graphs which captures some of the complex structure of circular-arc graphs and provides a more unified approach to designing efficient algorithms for solving problems on circular-arc graphs. ::: The problem of recognizing circular-arc graphs was initially conjectured to be NP-Complete and the question remained open for about sixteen years. In 1980, Alan Tucker proved the conjecture false by devising an $O(n\sp3)$ time algorithm. We exploit the relationship between circular-arc graphs and chordal bipartite graphs to achieve an $O(n\sp2)$ time circular-arc graph recognition algorithm which is simpler than Tucker's algorithm. We retain the overall structure of Tucker's algorithm, but introduce new techniques in each of the parts. The algorithm employs a new $O(n\sp2)$ time method for computing neighborhood containment relations in circular-arc graphs, and reductions to the recognition problem on two clique coverable circular-arc graphs. ::: As further applications of the relationship between circular-arc graphs and chordal bipartite graphs, we present an $O(n\sp2)$ isomorphism test for two clique coverable circular-arc graphs, a new $O(n\sp2)$ time algorithm to compute neighborhood intersection relations in circular-arc graphs, and we improve the time complexity of generating all maximum cliques of a circular-arc graph. <s> BIB003 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> General Circular-Arc Graphs <s> A graph G is a circular-arc graph if it is the intersection graph of a set of arcs on a circle. That is, there is one arc for each vertex of G, and two vertices are adjacent in G if the corresponding arcs intersect. We give a linear time bound for recognizing this class of graphs. When G is a member of the class, the algorithm gives a certificate in the form of a set of arcs that realize it. <s> BIB004 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> General Circular-Arc Graphs <s> In this work we present three new recognition algorithms for circular-arc graphs and for two subclasses of this graph class. We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad [ES93, Esc97]. Our algorithm is simpler than the earlier linear-time recognition algorithm of McConnell [McC03], which is the only linear time recognition algorithm previously known. We give new characterizations of proper circular-arc graphs and of unit circular-arc graphs which are based on characterizations of Tucker [Tuc71, Tuc74]. These characterizations lead to two new linear-time algorithms for recognizing proper circular-arc graphs and for recognizing unit circular-arc graphs. Both algorithms either provide a model for the input graph, or a certificate that such a model does not exist. No other previous algorithm for each of these two graph classes provides a certificate for its result. <s> BIB005 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> General Circular-Arc Graphs <s> We give a linear-time recognition algorithm for circular-arc graphs based on the algorithm of Eschen and Spinrad (Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 128–137, 1993) and Eschen (PhD thesis, 1997). Our algorithm both improves the time bound of Eschen and Spinrad, and fixes some flaws in it. Our algorithm is simpler than the earlier linear-time recognition algorithm of McConnell (Algorithmica 37(2):93–147, 2003), which is the only linear time recognition algorithm previously known. <s> BIB006
In this section, we discuss the recognition of general circular-arc graphs. Circular-arc graphs have been characterized by Tucker in terms of circular orderings of its vertices, as follows.  The question of recognizing circular-arc graphs has been first posed by Hadwiger, Debrunner and Klee, in 1964  . Tucker who described the first polynomial time algorithm BIB001 for it. The complexity of this algorithm is O(n 3 ). The general outline of this method has been somehow also employed in the later algorithms. A key concept of this method can be described in terms of matrices, as follows. Let G be a graph. For our purpose, there is no loss of generality to consider that G has no twins. The intersection matrix of G is a n × n matrix λ, where each entry λ ij informs the type of intersection, if any, between N[ , and As an example, Figure 3 (b) shows an intersection matrix of the graph of Figure 3 (a). The idea is to try to establish a similarity between neighborhood relations of the vertices of the graph G, and relations among the arcs that would correspond to the vertices of G, in the assumption that G is a circulararc graph. We switch from a graph to a model. Let M = (C, A) be a CA model. The intersection matrix of M is an n × n matrix µ, where µ ij expresses the type of relation between A i and A j , where A i , A j ∈ A, as: So, given a graph G, the basis of the methods   BIB006 BIB004 BIB001 is to construct an intersection matrix λ of G, and use it for guiding the construction of a CA model of G, if one exists. That is, the model that is looked for is one whose intersection matrix is precisely λ. The following theorem asserts that this is always possible, whenever G is a CA graph. Theorem 2 ( BIB001  ): Let G be a graph with no universal vertex, nor twins. Then an intersection matrix of G is an intersection matrix of some CA model of G. Consequently, the initial step of a recognition algorithm for CA graphs would be to compute the intersection matrix of the input graph G. The algorithm BIB001 considers two cases, namely G being co-bipartite, or not. Each of the cases is handled separately. When G is not co-bipartite, the method consists of looking for an independent set of G. Again there are two cases to consider, namely when this independent set is of size 3, or greater than 3. In both situations, the basic principle is to allocate a set of pairwise disjoint arcs, to correspond to the independent set. Subsequently, other arcs are placed into the model, which is refined, step by step. The algorithm BIB001 performs these operations in O(n 3 ) time. Eschen and Spinrad  described improved methods, which lowered the complexity to O(n 2 ). See Eschen BIB003 . Nussbaum BIB005 pointed out that the above mentioned method to allocate the pairwise disjoint arcs ought to be modified. In fact in his M.Sc Thesis BIB005 , he described the required correction. Recently, Kaplan and Nussbaum BIB006 improved the allocation of the disjoint arcs, so to perform it in linear time. Furthermore, in BIB006 a shaper analysis of Eschen and Spinrad's algorithm is formulated, showing that in fact they run in linear time. Spinrad BIB002 described an elegant method for handling the case where G is co-bipartite. Let The following theorem characterizes co-bipartite CA graphs G, in terms of the digraphs D G . The above theorem leads directly to an algorithm for recognizing co-bipartite CA graphs of complexity O(n 3 ). Eschen and Spinrad  reduced the complexity to linear time, by describing an algorithm for computing intersection matrices in O(n 2 ) time and employing a convenient chordal bipartite graph. Note that m = Ω(n 2 ), given that G is co-bipartite. Hsu  formalized the basis of the existing recognition algorithms for CA graphs, through Theorem 2. Hsu's recognition algorithm employs the idea of intersection matrices to construct a canonical model for the input graph G. Such a model is then transformed into a circle graph, that is, an interesction graph of chords of a circle. The problem of recognizing CA graphs is then reduced to the recognition of circle graphs. An algorithm for recognizing circle graphs is described in  and is employed in the CA graph recognition process. The method uses different kinds of decompostion techniques, such as modular decompostion and join decomposition. Besides describing recognition algorithms for circle graphs and CA graphs,  formulates isomorphism algorithms for both classes. The overall complexity is O(nm). The algorithm by McConnell BIB004 also employs the reduction to chordal bipartite graphs  for constructing the intersection matrix. However, BIB004 uses a sharper analysis, and shows that the computation can be done in linear time. The algorithm employs arc flippings, that is, replacing arcs with their complements. It also applies this notion to intersection matrices, as follows. Let µ be a n × n intersection matrix, and 1 ≤ i ≤ n. The complement of µ, relative to i, denoted by µ i is the matrix obtained from µ by possibly changing each element of row i and column i, as follows: Observe that the complement of µ, relative to i, reflects the changes in a possible CA model M = (C, A) produced by complementing arc A i ∈ A. The notion of complement relative to a row is further generalized to subsets, as follows. Let I = {i 1 , . . . , i k } ⊆ {1, . . . , n}. The complement of µ, relative to I, denoted by µ I is the matrix obtained from µ by iterating the operations of taking complements, for each j ∈ I. That is, first consider the complement of µ, relative to i j . Then take the complement of µ i 1 , relative to i 2 , and so on, until i k is considered. Again, (µ I ) I = µ. In order to compute the complement µ I of an intersection matrix µ, relative to some subset I, we consider the set M of complement matrices, obtained by iteratively taking the required complements. Call M a complement related family of matrices. The theorem below describes two properties of complement related families. The term interval matrix refers to an intersection matrix of an interval graph or model. Property (ii) of this theorem means that given any intersection matrix of a CA graph, it is always possible to find a subset of indices I, such that µ I is an interval matrix. The outline of algorithm BIB004 is as follows: Let G be a CA graph with no universal vertices, nor twins. (1) Construct an intersection matrix µ of G. (2) Find the complement µ I , relative to a chosen I ⊆ {1, . . . , n}, so that µ I is an interval matrix. Note that the algorithm may fail to perform one of the above steps, in which case the graph is not CA. Conversely, if G is not a CA graph and the algorithm reaches Step 5, then it would report failure in this step. However, this could also be possibly detected in some previous step. For computing Step 1, basically employ the method of evaluating neighborhoods of  , which BIB004 shows can be performed in linear time. The aim of Step 2 is to transform µ into an interval matrix µ I . With this purpose, we have to choose properly the set I of indices. Keeping in mind that the aim is to obtain a linear time algorithm, I should be restricted to have O(m/n) size. This ensures that complementing the members of I to obtain µ I from µ would take O(m) time. The details to actually constructing such a set I can be found in  . In Steps 1 and 2, we still deal with intersection matrices of graphs. Step 3 represents the change to intersection matrices of models. If G is a CA graph, in Step 3 we obtain an interval model. The method is not simple and involves the application of tools as transitive orientations, modular decompositions and partitionings. The computation of Step 4 is straightforward. Finally, Step 5 requires to verify if a given model M is a CA model of a given graph G. Also, there is no difficulty to compute it. McConnell BIB004 showed that all the above steps can be implemented in O(n + m) time.