Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> For <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> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> For <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> BIB002
Step 1, apply the algorithm by McConnell BIB001 or that by Kaplan and Nussbaum BIB002 which output a CA model M for G, or report that G is not CA. It should be observed that the algorithm BIB002 outputs a stable model of G, in case G is CA. However, to include the case where the graph might be given by an arbitrary CA model of it, we report on the algorithm for transforming any CA model into a stable one, corresponding to Step 2, as below described. The basic idea of the method for transforming M into a stable model is to increase as much as possible the lengths of the arcs, by possibly extending both of its extremes, while maintaining the adjacencies of the corresponding graph. A possible strategy for accomplishing it is first to extend the end points t j of the arcs of A. That is, for each t j , we find the closest start point s i , in the clockwise direction, satisfying i = j or A i ∩ A j = ∅. Then we move t j so as to become the extreme point just before s i , clockwise. After considering all end points, we possibly extend the start points, as follows. For each s i , determine the closest end point t j , in the counterclockwise direction, satisfying i = j or A i ∩ A j = ∅. Let T = SEQUENCE(t j ). Then move t j towards T , counterclockwise, possibly reordering T and transforming this sequence into T ′ s i T ", where T ′ is the set of end points t k ∈ T , such that i = k or A i ∩ A k = ∅, while T " = T \ T ′ . This algorithm transforms M into a stable model. A consequence of it is the following.