Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> The widespread occurrence of genetic circularity suggests a selective advantage to map circularity per se. Circularity permits gene clustering relations not possible in linear maps; that is, every gene in a circular map can have two nearest map neighbors, two next nearest, etc. It seems possible that map circularity is a consequence of the selective forces responsible for the clustering of genes of related function. Certain features of the pattern of crossing-over in various fungi suggest that circularity of linkage maps is there to be found. A concurrence of high frequencies of second-division segregation and negative chromatid interference across the centromere, both of which phenomena have been reported, is a feature of a simple hypothetical crossover pattern that generates circular linkage maps. <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <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> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <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> BIB003 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> A standard problem in combinatorial theory is to characterize structures which satisfy a certain property by providing a minimum list of forbidden substructures, for example, Kuratowski's well known characterization of planar graphs. In this paper, we establish connections between characterization problems for interval graphs, circular are graphs, comparability graphs, planar lattices, 0–1 matrices, interval orders, partially ordered sets with dimension at most two, partially ordered sets with interval dimension at most two, and related problems involving the representation of families of finite sets by points or intervals of the real line. We use these connections to determine the collection of all 3-irreducible posets. We are then able to determine the collection of all 3-interval irreducible posets of height one and the set of all forbidden subgraphs with clique covering number two in the characterization of circular are graphs. <s> BIB004 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> An undirected graph is called a circular-arc graph if there exists a family F 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. Circular-arc graphs have recently been applied to problems in multi-dimensional scaling, computer compiler design, and the characterization of a certain class of lattices. An efficient algorithm for recognizing a circular-arc graph is outlined. <s> BIB005 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <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> BIB006 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> Algorithmic Graph Theory and Perfect Graphs, first published in 1980, has become the classic introduction to the field. This new Annals edition continues to convey the message that intersection graph models are a necessary and important tool for solving real-world problems. It remains a stepping stone from which the reader may embark on one of many fascinating research trails. The past twenty years have been an amazingly fruitful period of research in algorithmic graph theory and structured families of graphs. Especially important have been the theory and applications of new intersection graph models such as generalizations of permutation graphs and interval graphs. These have lead to new families of perfect graphs and many algorithmic results. These are surveyed in the new Epilogue chapter in this second edition. New edition of the "Classic" book on the topic Wonderful introduction to a rich research area Leading author in the field of algorithmic graph theory Beautifully written for the new mathematician or computer scientist Comprehensive treatment <s> BIB007 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> Comparability graphs are undirected graphs that represent the comparability relation of partial orders. They constitute an important interface between graphs and partial orders both for theoretical investigations on their structural properties, and the development of efficient algorithmic methods for otherwise NP-hard combinatorial (optimization) problems on partial orders and their comparability graphs. <s> BIB008 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> A module of an undirected graph is a set X of nodes such for each node x not in X, either every member of X is adjacent to x, or no member of X is adjacent to x. There is a canonical linear-space representation for the modules of a graph, called the modular decomposition. Closely related to modular decomposition is the transitive orientation problem, which is the problem of assigning a direction to each edge of a graph so that the resulting digraph is transitive. A graph is a comparability graph if such an assignment is possible. We give O(n+m) algorithms for modular decomposition and transitive orientation, where n and m are the number of vertices and edges of the graph. This gives linear time bounds for recognizing permutation graphs, maximum clique and minimum vertex coloring on comparability graphs, and other combinatorial problems on comparability graphs and their complements. c 1999 Published by Elsevier Science B.V. All rights reserved <s> BIB009 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> In this paper we study a periodic allocation problem which is a generalization of the dynamic storage allocation problem to the case in which the arrival and departure time of each item is periodically repeated. These problems are equivalent to the interval coloring problem on weighted graphs in which each feasible solution corresponds to an acyclic orientation, and the solution value is equal to the length of the longest weighted path of the oriented graph. Optimal solutions correspond to acyclic orientations having the length of longest weighted path as small as possible. We prove that for the interval coloring problem on a class of circular arc graphs, and hence for a periodic allocation problem, there exists an approximation algorithm that finds a feasible solution whose value is at most two times the optimal. <s> BIB010 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <s> Combinatorial auctions (CAs) are important mechanisms for allocating interrelated items. Unfortunately, winner determination is NP-complete unless there is special structure. We study the setting where there is a graph (with some desired property), with the items as vertices, and every bid bids on a connected set of items. Two computational problems arise: 1) clearing the auction when given the item graph, and 2) constructing an item graph (if one exists) with the desired property. 1 was previously solved for the case of a tree or a cycle, and 2 for the case of a line graph or a cycle. ::: ::: We generalize the first result by showing that given an item graph with bounded treewidth, the clearing problem can be solved in polynomial time (and every CA instance has some treewidth; the complexity is exponential in only that parameter). We then give an algorithm for constructing an item tree (treewidth 1) if such a tree exists, thus closing a recognized open problem. We show why this algorithm does not work for treewidth greater than 1, but leave open whether item graphs of (say) treewidth 2 can be constructed in polynomial time. We show that finding the item graph with the fewest edges is NP-complete (even when a graph of treewidth 2 exists). Finally, we study how the results change if a bid is allowed to have more than one connected component. Even for line graphs, we show that clearing is hard even with 2 components, and constructing the line graph is hard even with 5. <s> BIB011 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <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> BIB012 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <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> BIB013 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Introduction <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> BIB014
Circular-arc graphs are the intersection graphs of arcs on a circle. Early papers, considering this class have been written by Hadwiger, Debrunner and Klee in 1964  and by Klee in 1969  . Tucker wrote his PhD thesis on this class in 1969  , and in the 1970's published a series of articles  BIB002 BIB003 BIB005 BIB006 containing some fundamental properties on circular-arc graphs and subclasses. These graphs have since received considerable attention for a few reasons, their beatiful structure being one of them. There are applications of circular-arc graphs in areas as genetics, traffic control and many others. See  BIB010 BIB011   BIB001  BIB004 BIB005 for applications. Circular-arc graphs are a generalization of interval graphs, the intersection graphs of intervals on a real line. However, in general, problems for circulararc graphs tend to be more difficult than for interval graphs. One of the reasons is that intervals of a real line satisfy the Helly property, while arcs of a circle do not necessarily satisfy it. This implies that the maximal cliques of an interval graph can be associated to chosen points of the line. The latter means that an interval graph can have no more maximal cliques than vertices. In contrast, circular-arc graphs may contain maximal cliques which do not correspond to points of the circle. In fact, circular-arc graphs can have an exponential number of maximal cliques. Complements of induced matchings are examples of such graphs. In the present paper, we survey some structural characterizations and recognition algorithms for circular-arc graphs and subclasses of these graphs. The emphasis is on linear time recognition algorithms, both for this class and subclasses of it. It is worth mentioning that in the last year, at least five papers appeared in conference proceedings, describing linear time algorithms for circular-arc graphs and subclasses  BIB014 BIB012 BIB013  . The books by Spinrad  and by Golumbic BIB007 contain comprehensive accounts on the class. See also the books  BIB009 and the article BIB008 . The following is the plan of the paper. In the next section, we describe the basic definitions and notation. Section 3 contains some characterizations and recognition algorithms for circular-arc graphs. The subclasses are examined in the following sections. That is, characterizations and recognition algorithms for the classes of proper circular-arc graphs, unit circular-arc graphs and Helly circular-arc graphs are presented in Sections 4, 5 and 6 respectively. Co-bipartite circular-arc graphs and other subclasses are considered in Sections 7 and 8. Some open problem are formulated in the last section, which contains a summary of the results.