Home > 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.

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.