A binary matrix has the Consecutive Ones Property (COP) for rows if its columns can be permuted such that all the ones in each row are consecutive [22]. See Figure 2 for an example of a matrix with the COP. Determining whether a matrix has the COP and computing the permutation of the columns that proves this property has applications in a number of areas including testing for graph planarity [22] and recognizing interval graphs [22,23]. Booth and Leuker [22] describe a data structure called the PQ tree which they use to represent all legal permutations of column orderings in a matrix with the COP property. They prove that the PQ tree and the correct column permutation can be computed in time linear in the number of ones in the matrix.