Editing PQ tree

{{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}}

==Examples and notation==
[[Image:pq-tree-5-leaves.svg|left|thumb|The PQ tree representing 
<br/>[1 (2 3 4) 5] ]]

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

Where graphical presentation is unavailable PQ trees are often noted using nested parenthesized lists.  Each matched pair of square parentheses represents a Q node and each matched pair of rounded parentheses represent a P node.  Leaves are non-parentheses elements of the lists.  The image on the left is represented in this notation by [1 (2 3 4) 5]. This PQ tree represents the following twelve permutations on the set {1, 2, 3, 4, 5}:
: 12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.

==PC trees==

The '''PC tree''', developed by [[Wei-Kuan Shih]] and [[Wen-Lian Hsu]], is a more recent generalization of the PQ tree. Like the PQ tree, it represents permutations by reorderings of nodes in a tree, with elements represented at the leaves of the tree. Unlike the PQ tree, the PC tree is unrooted. The nodes adjacent to any non-leaf node labeled P may be reordered arbitrarily as in the PQ tree, while the nodes adjacent to any non-leaf node labeled C have a fixed [[cyclic order]] and may only be reordered by reversing this order.  Thus, a PC tree can only represent sets of orderings in which any circular permutation or reversal of an ordering in the set is also in the set. However, a PQ tree on ''n'' elements may be simulated by a PC tree on ''n'' + 1 elements, where the extra element serves to root the PC tree.  The data structure operations required to perform a [[planarity testing]] algorithm on PC trees are somewhat simpler than the corresponding operations on PQ trees.{{r|sh99}}

==See also==
*[[Series-parallel partial order]]

==References==
{{reflist|refs=

<ref name=bl76>{{cite journal
 | last1 = Booth | first1 = Kellogg S.
 | last2 = Lueker | first2 = George S.
 | doi = 10.1016/S0022-0000(76)80045-1 | doi-access = free
 | issue = 3
 | journal = [[Journal of Computer and System Sciences]]
 | pages = 335–379
 | title = Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
 | volume = 13
 | year = 1976}}</ref>

<ref name=k93>{{cite conference
 | last = Karp | first = Richard M. | author-link = Richard M. Karp
 | editor1-last = Kosaraju | editor1-first = S. Rao | editor1-link = S. Rao Kosaraju
 | editor2-last = Johnson | editor2-first = David S. | editor2-link = David S. Johnson
 | editor3-last = Aggarwal | editor3-first = Alok
 | contribution = Mapping the genome: some combinatorial problems arising in molecular biology
 | doi = 10.1145/167088.167170
 | pages = 278–285
 | publisher = Association for Computing Machinery
 | title = Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA
 | title-link = Symposium on Theory of Computing
 | year = 1993}}</ref>

<ref name=sh99>{{cite journal
 | last1 = Shih | first1 = Wei-Kuan
 | last2 = Hsu | first2 = Wen-Lian
 | doi = 10.1016/S0304-3975(98)00120-0 | doi-access = free
 | issue = 1-2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | pages = 179–191
 | title = A new planarity test
 | url = https://www.iis.sinica.edu.tw/IASL/webpdf/paper-1999-A_New_Planarity_test.pdf
 | volume = 223
 | year = 1999}}</ref>

}}

==External links==
*[https://gregable.com/2008/11/pq-tree-algorithm.html PQ Tree Algorithm and Consecutive Ones Problem]
*[https://pref.tools/pqtree#001010&011010&011101 Javascript demo of PQ Trees]

{{CS-Trees}}

{{DEFAULTSORT:Pq Tree}}
[[Category:Trees (data structures)]]