Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Other classes <s> Primarily intended for research mathematicians and computer scientists, Combinatorics and Partially Ordered Sets: Dimension Theory also serves as a useful text for advanced students in either field. William Trotter concentrates on combinatorial topics for finite partially ordered sets, and with dimension theory serving as a unifying theme, research on partially ordered sets or posets is linked to more traditional topics in combinatorial mathematics -- including graph theory, Ramsey theory, probabilistic methods, hypergraphs, algorithms, and computational geometry. The book's most important contribution is to collect, organize, and explain the many theorems on partially ordered sets in a way that makes them available to the widest possible audience.Chapters: Introduction to Dimension ? Crowns, Splits, Stacks, Sums and Products ? Characterization Problems for Posets, Lattices, Graphs, and Families of Sets ? Hypergraph Coloring, Computational Complexity, and Irreducible Posets ? Planar Posets and Trees ? Planar Graphs, Planar Maps and Convex Polytopes ? Probabilistic Methods in Dimension Theory ? Interval and Geometric Containment Orders ? Greedy Dimension, Back-Tracking, and Depth First Search ? Products of Chains of Bounded Length ? Large Minimal Realizers <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Other classes <s> A circular-arc graph is the intersection graph of arcs on a circle. A Helly circular-arc graph is a circular-arc graph admitting a model whose arcs satisfy the Helly property. A clique-independent set of a graph is a set of pairwise disjoint cliques of the graph. It is NP-hard to compute the maximum cardinality of a clique-independent set for a general graph. In the present paper, we propose polynomial time algorithms for finding the maximum cardinality and weight of a clique-independent set of a 3K2-free CA graph. Also, we apply the algorithms to the special case of an HCA graph. The complexity of the proposed algorithm for the cardinality problem in HCA graphs is O(n). This represents an improvement over the existing algorithm by Guruswami and Pandu Rangan, whose complexity is O(n2). These algorithms suppose that an HCA model of the graph is given. <s> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Other classes <s> A circular-arc model M=(C,A) is a circle C together with a collection A of arcs of C. If no arc is contained in any other then M is a proper circular-arc model, if every arc has the same length then M is a unit circular-arc model and if A satisfies the Helly Property then M is a Helly circular-arc model. A (proper) (unit) (Helly) circular-arc graph is the intersection graph of the arcs of a (proper) (Helly) circular-arc model. Circular-arc graphs and their subclasses have been the object of a great deal of attention in the literature. Linear time recognition algorithms have been described both for the general class and for some of its subclasses. In this article we study the circular-arc graphs which admit a model which is simultaneously proper and Helly. We describe characterizations for this class, including one by forbidden induced subgraphs. These characterizations lead to linear time certifying algorithms for recognizing such graphs. Furthermore, we extend the results to graphs which admit a model which is simultaneously unit and Helly, also leading to characterizations and a linear time certifying algorithm. <s> BIB003 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Other classes <s> A clique-transversal of a graph G is a subset of vertices intersecting all the cliques of G. It is NP-hard to determine the minimum cardinality τ c of a clique-transversal of G. In this work, first we propose an algorithm for determining this parameter for a general graph, which runs in polynomial time, for fixed τ c . This algorithm is employed for finding the minimum cardinality clique-transversal of \(\overline{3K_{2}}\) -free circular-arc graphs in O(n 4) time. Further we describe an algorithm for determining τ c of a Helly circular-arc graph in O(n) time. This represents an improvement over an existing algorithm by Guruswami and Pandu Rangan which requires O(n 2) time. Finally, the last proposed algorithm is modified, so as to solve the weighted version of the corresponding problem, in O(n 2) time. <s> BIB004 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Other classes <s> Abstract A circular-arc graph is the intersection graph of a set of arcs on the circle. It is a Helly circular-arc graph if it has a Helly model , where every maximal clique is the set of arcs that traverse some clique point on the circle. A clique model is a Helly model that identifies one clique point for each maximal clique. A Helly circular-arc graph is proper if it has a Helly model where no arc is a subset of another. In this paper, we show that the clique intersection graphs of Helly circular-arc graphs are related to the proper Helly circular-arc graphs. This yields the first polynomial (linear) time recognition algorithm for the clique graphs of Helly circular-arc graphs. Next, we develop an O ( n ) time algorithm to obtain a clique model of Helly model, improving the previous O ( n 2 ) bound. This gives a linear-time algorithm to find a proper Helly model for the clique graph of a Helly circular-arc graph. As an application, we find a maximum weighted clique of a Helly circular-arc graph in linear time. <s> BIB005 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Other classes <s> A circular-arc graph is the intersection graph of a family of arcs on a circle. A characterization by forbidden induced subgraphs for this class of graphs is not known, and in this work we present a partial result in this direction. We characterize circular-arc graphs by a list of minimal forbidden induced subgraphs when the graph belongs to any of the following classes: P4 -free graphs, paw-free graphs, claw-free chordal graphs and diamond-free graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 289–306, 2009 <s> BIB006
In this section, we consider some other classes of circular arc graphs. It seems natural to consider the classes of CA graphs admitting a model which simultaneously satisfies two of the models PCA, UCA and HCA. Recall that the latter are the main models of CA graphs and are defined by imposing some restriction directly on the arcs of the model. Clearly, PCA graphs contain UCA graphs, so we only need to consider models simultaneously PCA and HCA, and UCA and HCA. Lin, Soulignac and Szwarcfiter BIB003 have defined a proper Helly circulararc (PHCA) graph, as a graph admitting a model which is simultaneously proper and Helly. Observe that a graph G may be simultaneously PCA and HCA, but not PHCA. The following is a characterization of PHCA graphs, by forbidden induced subgraphs. Theorem 34 ([40] ): Let G be a PCA graph. Then G is PHCA if and only it contains neither the Hajós graph nor the 4-wheel as an induced subgraph. Another characterization described in BIB003 leads to a linear time algorithm for recognizing PHCA graphs. The algorithm also produces certificates, both positive and negative, within the same bound. Similar results were also described in the above paper, for the class of graphs admitting a model which is simultaneously UCA and HCA. Subclasses of CA graphs can also be obtained by imposing restrictions on the actual graphs, instead of on the models. In this way, CA graphs which also belong to some other known class have been studied. More recently, Bonomo, Durán, Grippo and Safe BIB006 characterized four subclasses of CA graphs, each of them formed by graphs simultaneously belonging to well known classes. All the characterizations are in terms of minimal forbidden induced subgraphs. The following is a characterization for a P 4 -free graph to be a CA graph. Denote by G 0 and G 1 the graphs obtained from G, by adding an additional vertex adjacent to no vertex of G and to exactly one vertex of it, respectively. In BIB006 , characterizations have also been described for a K 1,3 -free graph to be a CA graph, for a K 1 3 -free graph to be a CA graph and for a (K 4 − e)-free graph to be a CA graph. Some subclasses of CA graphs have been considered, in relation to specific problems. Trotter BIB001 has proved that a partial order of a CA comparability graph has dimension at most 4. Durán, Lin, Mera and Szwarcfiter BIB002 BIB004 have described polynomial time algorithms for finding maximum cliqueindependent sets and minimum clique-transversals in 3K 2 -free CA graphs. Lin, McConnell, Soulignac and Szwarcfiter BIB005 have studied the clique structure of HCA graphs. Finally, we mention that some other classes of graphs are closely related to CA graphs. Among them we mention circular-arc containment graphs (Nirkhe  , c.f.  ) and circular-arc digraphs (Sen, Das and West  ).