PQ tree

A PQ tree is a rooted, labeled tree that represents a family of permutations of a set of elements, so that one compact structure stands for many allowed orderings. Each element is a leaf, and every inner node is labeled P or Q. The children of a P node may be arranged in any order, while the children of a Q node may only be kept in order or reversed. The set of orderings the tree stands for is every leaf order reachable by any sequence of those two moves. Kellogg Booth and George Lueker discovered and named it in 1976. Algorithms use it for ordering problems with constraints: each constraint is applied one at a time by reshaping the tree until it admits only orderings that satisfy it. Stated uses include building a contig map from DNA fragments, testing a matrix for the consecutive ones property, recognizing interval graphs and deciding whether a graph is planar. The unrooted PC tree of Shih and Hsu is a later generalization that fixes cyclic rather than linear order.