We will use the recognition algorithm for proper interval graph \(H=(V^\prime ,E^\prime )\)  given by Booth and Lueker [1]} as a blackbox that runs in \(O(|V^\prime |+|E^\prime |)\) . The main idea of their algorithm is that \(H\)  is a proper interval graph if and only if the adjacency matrix of the graph satisfies the consecutive 1's property. In other words, \(H\)  is a proper interval graph if and only if there is an ordering of the vertices of \(H\)  such that for any vertices \(v\)  in \(H\) , the neighbors of \(v\)  must be consecutive in that ordering. So for every vertex \(v\)  in \(H\)  they consider restrictions, on the ordering of the vertices, of the form “all vertices in the neighborhood of \(v\)  must be consecutive". This is done using the data structure of \(PQ\) -trees.
The PQ-tree helps to store all the possible orderings that respect all these kind of restrictions. It is important to note that all the orderings that satisfy all the restrictions are precisely all the canonical orderings of vertices of \(H\) .
