Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 13 ([65] <s> A 0-1 matrix has the consecutive-ones property if its columns can be ordered so that the ones in every row are consecutive. It has the circular-ones property if its columns can be ordered so that, in every row, either the ones or the zeros are consecutive. PQ trees are used for representing all consecutive-ones orderings of the columns of a matrix that have the consecutive-ones property. We give an analogous structure, called a PC tree, for representing all circular-ones orderings of the columns of a matrix that has the circular-ones property. No such representation has been given previously. In contrast to PQ trees, PC trees are unrooted. We obtain a much simpler algorithm for computing PQ trees that those that were previously available, by adding a zero column, x, to a matrix, computing the PC tree, and then picking the PC tree up by x to root it. <s> BIB001 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 13 ([65] <s> We give a forbidden substructure characterization of set families that have the consecutive-ones property, and a linear time algorithm to find the forbidden substructure if a set family does not have the property. The forbidden substructure has size O(n), where n is the size of the domain. The PQ tree is a well-known data structure for representing all consecutive-ones orderings. We show that it is given by a substitution decomposition of arbitrary set families that has not been described previously. This observation gives a generalization of the PQ tree to arbitrary set families, and we give a linear-time algorithm to compute it. <s> BIB002 </s> Characterizations and recognition of circular-arc graphs and subclasses: A survey <s> Theorem 13 ([65] <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> BIB003
): Let G be a co-bipartite graph. Then G is a PCA graph if and only if G is a permutation graph. The algorithm  then recognizes co-bipartite PCA graphs G by deciding if G is a permutation graph. Since we know that G is bipartite, a simpler linear time algorithm can be applied to decide if G is indeed a permutation graph. Consequently, the overall complexity of this algorithm is O(n + m). Note that Theorems 8 and 13 imply that the classes of proper interval bigraphs and bipartite permutation graphs are equivalent. Moreover, these classes are also equivalent to bipartite asteroid-free graphs  . More recently, Kaplan and Nussbaum BIB003 described another linear time recognition algorithm for PCA graphs, aiming at producing certificates. Such algorithm again considers two cases. When G is not co-bipartite, Kaplan and Nussbaum also apply Tucker's characterization (Theorem 6). In this case, for obtaining a certificate for the circular consecutive 1's property, they employ the algorithm by McConnell BIB002 (see also BIB001 ). The algorithm BIB002 produces a certificate for the augmented adjacency matrix not having the consecutive 1's property. However, in this situation we need a relation between the consecutive 1's property and the circular consecutive 1's property. The following theorem provides this relation. BIB003 then exhibits a convenient forbidden structure.