Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 30 ([60]): <s> The Ferrers dimension of a digraph has been shown to be an extension of the order dimension. By proving a property of (finite) transitive Ferrers digraphs, we give an original proof of this above result and derive Ore's alternative definition of the order dimension. Still, the order dimension is proved to be 'polynomially equivalent' to the Ferrers dimension. <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 30 ([60]): <s> In this paper, we provide efficient algorithms for a number of closely related problems. They are: threshold number 2 on split graphs, Ferrers dimension 2, biorder dimension 2, interval dimension 2, and the trapezoid graph recognition problems. We show that all these problems can be reduced to the 2-chain subgraph cover problem in O(n2) time. By introducing a new algorithm to reduce a 2-chain subgraph cover problem to a partial order dimension 2 problem in O(n2) time, we find an O(n2) time algorithm to solve the 2-chain subgraph cover problem. As a consequence, all the previously mentioned problems can be solved in O(n2) time. No other algorithm known to the authors can solve any of these problems in the same time bound. <s> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 30 ([60]): <s> Abstract An interval bigraph is an undirected bipartite graph whose edge set is the intersection of the edge sets of an interval graph and the edge set of a complete bipartite graph on the same vertex set. A bipartite interval representation of an interval bigraph is given by a bipartitioned set of intervals for its vertices, such that vertices are adjacent if and only if the corresponding intervals intersect and belong to opposite sides of the bipartition. Interval digraphs are directed graphs defined by a closely related concept. Each vertex of an interval digraph is represented by two intervals on the real line, a source interval and a target interval. The directed arc ( u , v ) exists in the interval digraph if the source interval of u meets the target interval of v . We give a dynamic programming algorithm recognizing interval bigraphs (interval digraphs) in polynomial time. This algorithm recursively constructs a bipartite interval representation of a graph from bipartite interval representations of proper subgraphs. Moreover, we list some forbidden substructures of interval bigraphs. <s> BIB003 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 30 ([60]): <s> , H, and lists \(\), a list homomorphism of G to Hwith respect to the listsL is a mapping \(\), such that \(\) for all \(\), and \(\) for all \(\). The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists \(\), \(\), admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs of clique covering number two. <s> BIB004
A graph G is a co-bipartite CA graph if and only if G can be oriented as an interval containment digraph. Another approach for describing co-bipartite CA graphs, employs the following concept introduced by Gutman  and Riguet  . A Ferrers digraph is a digraph D, where Cogis BIB001 related the Ferrers dimension to partial order dimension. Ferrers dimension can also be directly related to interval dimension and to trapezoid graphs; see Spinrad  , and Ma and Spinrad BIB002  . Co-bipartite CA graphs have also been employed in the problem of list homomorphisms to a fixed graph H. This problem can be solved in polynomial time when H is a co-bipartite CA graph, and it is NP-complete otherwise BIB004 . Hell and Huang have shown that a special class of co-bipartite CA graphs is closely related to interval bigraphs. It should be noted that Müller BIB003 , described a polynomial time algorithm for recognizing interval bigraphs. The complexity of it is O(n 5 m 6 log n). However, no algorithm with lower complexity is known so far, for this recognition problem. The class of co-bipartite proper CA graphs has been characterized by Hell and Huang, in terms of forbidden subgraphs. Theorem 33 ([26] ): Let G be a co-bipartite graph. Then G is a proper CA graph if and only if G does not contain an induced cycle of length at least 6, or any of the graphs H 2 , H 4 and H 5 of Figure 4 .