PQ tree
|
|
A PQ tree is a special kind of tree data structure. It is a rooted, labeled tree, with non-leaf nodes 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 a set of possible orderings for the leaf nodes. The children of a P node can be reordered in any way. The children of a Q node can be put in reverse order. A PQ tree represents all leaf node orderings that can be achieved by any sequence of these two operations.
Examples: If all the leaves of a PQ tree are connected directly to a root P node then all possible orderings are allowed. If all the leaves are connected directly to a root Q node then only one order (and its reverse) is allowed. If nodes a,b,c connect to a P node, which connects to a root P node, with all other leaf nodes connected directly to the root, then any ordering where a,b,c are contiguous is allowed. A PQ tree with many P and Q nodes can represent complicated subsets of the set of all possible orderings.
PQ trees are used to solve problems where the goal is to find an ordering that satisfies various constraints. Creating a contig map from DNA fragments is one example. Determining if a graph is planar is another. Note that embedding a graph in the plane determines a clockwise ordering for the neighbors of each node.
Reference
K.S. Booth and G.S. Lueker. Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity Using PQ- Tree Algorithms. Journal of Computer and Systems Sciences, 13:335-379, 1976.