Editing PQ tree (section)

{{Short description|Data structure for permutations}}
A '''PQ tree''' is a tree-based [[data structure]] that represents a family of [[permutation]]s on a set of elements, discovered and named by [[Kellogg S. Booth]] and [[George S. Lueker]] in 1976.{{r|bl76}} It is a rooted, labeled tree, in which each element is represented by one of the [[leaf node]]s, and each [[non-leaf node]] is labelled P or Q. A P node has at least two children, and a Q node has at least three children.

A PQ tree represents its permutations via permissible reorderings of the children of its nodes. The children of a P node may be reordered in any way. The children of a Q node may be put in reverse order, but may not otherwise be reordered. A PQ tree represents all leaf node orderings that can be achieved by any sequence of these two operations. A PQ tree with many P and Q nodes can represent complicated subsets of the set of all possible orderings. However, not every set of orderings may be representable in this way; for instance, if an ordering is represented by a PQ tree, the reverse of the ordering must also be represented by the same tree.

PQ trees are used to solve problems where the goal is to find an ordering that satisfies various constraints. In these problems, constraints on the ordering are included one at a time, by modifying the PQ tree structure in such a way that it represents only orderings satisfying the constraint.  Applications of PQ trees include creating a [[Contig|contig map]] from [[DNA]] fragments,{{r|k93}} testing a matrix for the consecutive ones property, recognizing [[interval graph]]s, and determining whether a graph is [[Planar graph|planar]].{{r|bl76}}