Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 19 ([41]): A digraph is weakly eulerian if and only if each of its connected components is strongly connected. <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> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 19 ([41]): A digraph is weakly eulerian if and only if each of its connected components is strongly connected. <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> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 19 ([41]): A digraph is weakly eulerian if and only if each of its connected components is strongly connected. <s> In a recent paper, Duran, Gravano, McConnell, Spinrad and Tucker described an algorithm of complexity O(n2) for recognizing whether a graph G with n vertices is a unit circular-arc (UCA) graph. Furthermore the following open questions were posed in the above paper: (i) Is it possible to construct a UCA model for G in polynomial time? (ii) Is it possible to construct a model, whose extremes of the arcs correspond to integers of polynomial size? (iii) If (ii) is true, could such a model be constructed in polynomial time? In the present paper, we describe a characterization of UCA graphs which leads to linear time algorithms for recognizing UCA graphs and constructing UCA models. Furthermore, we construct models whose extreme of the arcs correspond to integers of size O(n). The proposed algorithms provide positive answers to the three above questions. <s> BIB003 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 19 ([41]): A digraph is weakly eulerian if and only if each of its connected components is strongly connected. <s> We give two new algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs. The algorithms either provide a model for the input graph, or a certificate that proves that such a model does not exist and can be authenticated in O(n) time. <s> BIB004 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 19 ([41]): A digraph is weakly eulerian if and only if each of its connected components is strongly connected. <s> In a recent paper, Duran et al. [J. Algorithms, 58 (2006), pp. 67-78] described an algorithm of complexity $O(n^2)$ for recognizing whether a graph $G$ with $n$ vertices and $m$ edges is a unit circular-arc (UCA) graph. Furthermore, the following open questions were posed in the above paper: (i) Is it possible to construct a UCA model for $G$ in polynomial time? (ii) Is it possible to construct a UCA model, whose extremes of the arcs correspond to integers of polynomial size? (iii) If (ii) is true, could such a model be constructed in polynomial time? In the present paper, we describe a characterization of UCA graphs, based on network circulations. The characterization leads to a different recognition algorithm and to answering these questions in the affirmative. We construct a UCA model whose extremes of the arcs correspond to integers of size $O(n)$. The proposed algorithms, for recognizing UCA graphs and constructing UCA models, have complexities $O(n+m)$. Furthermore, the complexities reduce to $O(n)$, if a proper circular-arc (PCA) model of $G$ is already given as the input, provided the extremes of the arcs are ordered. We remark that a PCA model of $G$ can be constructed in $O(n+m)$ time, using the algorithm by Deng, Hell, and Huang [SIAM J. Comput., 25 (1996), pp. 390-403]. Finally, we also describe a linear time algorithm for finding feasible circulations in networks with nonnegative lower capacities and unbounded upper capacities. Such an algorithm is employed in the model construction for UCA graphs. <s> BIB005 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 19 ([41]): A digraph is weakly eulerian if and only if each of its connected components is strongly connected. <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
The following corollary expresses a desired property for UCA models. Next we refer to the recognition problem. Tucker's proof of the forbidden subgraph characterization for UCA graphs, in fact constructs a UCA model, whenever the graph does not contain any of the forbidden subgraphs. Therefore such a construction leads to an actual recognition algorithm for the class. However, as reported in   , the process involves shrinking and lengthening of arcs, implying the manipulation of large integers. It is not known whether this process terminates in polynomial time. The first polynomial time regonition algorithm for UCA graph has been formulated by Durán, Gravano, McConnell, Spinrad and Tucker  . It is based on Tucker method BIB001 and applies Corollary 1. Fixing the arcs to have unit length, the idea is to determine upper and lower bounds for the length of the circle. The upper bound is the smallest n/k value, among all (n, k)-circuits, whereas the lower bound is the largest m/l among all (m, l)-independent sets. Since m/l ≤ n/k it follows that G is not a UCA if and only if m/l = n/k. The algorithm  constructs (n, k)-circuits by starting at every arc, and choosing as the next arc in the circuit, the neighbor arc which extends farthest in the model. For (m, l)-independent sets, the algorithm also starts at every possible arc, but simply chooses the next arc to be the first non neighbor arc, in the clockwise direction. For performing these operations, the algorithm  requires O(n 2 ) time, using union-find techniques. A linear time recognition algorithm has been described by Lin and Szwarcfiter BIB003 . It is a direct consequence of the characterizations of Theorems 18 and 19. Given a PCA graph G by a normal PCA model of it, the algorithm BIB003 constructs the corresponding full system, reduced system and the segment digraph D. Then, it finds the connected components of D and verifies if each of them is strongly connected. In the affirmative case, G is UCA, while in the negative, it is not. All these operations can be performed in O(n) time. Observe that for representing the full and reduced systems, we need just O(n) indices, that is, 4n − 4 indices for the full system and at most 4n for the reduced system. When G is given by its sets of vertices and edges, both algorithms,  and BIB003 , employ a recognition algorithm of PCA graphs for constructing a PCA model. Algorithms of complexity O(n + m) with this purpose have been described in BIB002 BIB006 . If the PCA model is not normal then we need an algorithm for transforming a given PCA model into a normal PCA model, while preserving the implied adjacencies. An algorithm with this purpose has been described in  , with complexity O(n 2 ). In BIB003 another algorithm has been formulated, with linear complexity O(n). Consequently, the complexity of the entire recognition algorithm BIB003 is O(n + m). This complexity reduces to O(n), whenever the graph is given by a PCA model of it. Kaplan and Nussbaum BIB004 described a recognition algorithm for UCA graphs, also based on Tucker's characterization BIB001 . Basically, it employs the same strategy as the algorithm  , that is, to compute upper and lower bounds for the circle length of a possible UCA model. However, instead of considering (n, k)-circuits and (m, l)-independents set starting at every arc of the model, the algorithm BIB004 , needs only to start from one of the vertices of these special subgraphs. In addition, BIB004 applies a generalization of (n, k)-circuits and (m, l)-independet sets, by allowing repetitions of vertices and employing paths, instead of cycles. These alterations allows BIB004 to decrease the complexity of the algorithm  from O(n 2 ) to O(n + m). In addition, the algorithm BIB004 is simpler than  . Besides recognizing UCA graphs. BIB004 contains an algorithm for exhibiting a negative certificate, that is a certificate for the case that the graph is PCA, but not UCA. This certificate is described in terms of a minimum (n, k)-circuit and maximum (m, l)-independent set, and requires O(n + m) time to be computed. Finally, for constructing UCA models, so far the only known algorithm is by Lin and Szwarcfiter BIB003 , described below. The algorithm BIB003 again employs the characterization of UCA graphs in terms of weakly eulerian digraphs, and the characterization of the latter digraphs in terms of strongly connected components, respectively Theorem 18 and 19. Given a graph G, let M be a normal PCA model of it. First consider the reduced system of equations. The idea is now to solve the system. The solution informs the required segment lengths that would lead to a UCA model. Then modify M accordingly, while perserving the circular ordering of its extreme points. The notation below is employed. An arborescence is a orientation of a tree. An out-arborescence (inarborescence) is a rooted arborescence where all edges are directed towards the leaves (root). The algorithm for the model construction, first runs the recognition algorithm. Let D be the segment digraph of G. The aim is to determine a weakly eulerian weighting for G. Consider each connected component B of D. We know that it induces a strongly connected component. To start, assign a unit weight w j to each of the edges e j of B. We need to increase conveniently some of the weights of the edges, so as to achieve w All the possible in-deficiencies are corrected by conveniently increasing the weights of the edges of an arbitrary spanning out-arborescence of B. Similarly, the out-deficiencies are eliminated, using a spanning in-arborescence of B. An incremental technique is employed for the weights assignments. The algorithm for the UCA model construction requires O(n) time, given a PCA model of the graph. All the weights constructed by the above algorithm are integers of size less than 4n BIB003 . This mean that the UCA model, obtained by the above construction, is such that its extreme points correspond to integers of size less than 4n. The results contained in BIB003 were extended and described in paper BIB005 . In fact, BIB005 reduces the problem of solving the reduced system to the problem of finding a feasible circulation in a network with non negative lower capacities and unbounded upper capacities. A linear time solution for the latter problem is then formulated, which corresponds to a generalization of the above described method for constructing UCA models.