PQ tree

<h2 id="examples-and-notation">Examples and notation</h2>

<p>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.
</p><p>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}:
</p>
12345, 12435, 13245, 13425, 14235, 14325, 52341, 52431, 53241, 53421, 54231, 54321.
<h2 id="pc-trees">PC trees</h2>
<p>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 <a href="/facts/Cyclic_order/j5DaU26j">cyclic order</a> 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 <i>n</i> elements may be simulated by a PC tree on <i>n</i> + 1 elements, where the extra element serves to root the PC tree.  The data structure operations required to perform a <a href="/facts/Planarity_testing/uVBsYdgf">planarity testing</a> algorithm on PC trees are somewhat simpler than the corresponding operations on PQ trees.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Series-parallel_partial_order/X8VP9aRR">Series-parallel partial order</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://gregable.com/2008/11/pq-tree-algorithm.html">PQ Tree Algorithm and Consecutive Ones Problem</a></li>
<li><a href="https://pref.tools/pqtree#001010&011010&011101">Javascript demo of PQ Trees</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Booth, Kellogg S.; Lueker, George S. (1976). "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms". Journal of Computer and System Sciences. 13 (3): 335–379. doi:10.1016/S0022-0000(76)80045-1. <a href="https://doi.org/10.1016%2FS0022-0000%2876%2980045-1" target="_blank">https://doi.org/10.1016%2FS0022-0000%2876%2980045-1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Karp, Richard M. (1993). "Mapping the genome: some combinatorial problems arising in molecular biology". In Kosaraju, S. Rao; Johnson, David S.; Aggarwal, Alok (eds.). Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA. Association for Computing Machinery. pp. 278–285. doi:10.1145/167088.167170. <a href="/wiki/Richard_M._Karp" target="_blank">/wiki/Richard_M._Karp</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Booth, Kellogg S.; Lueker, George S. (1976). "Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms". Journal of Computer and System Sciences. 13 (3): 335–379. doi:10.1016/S0022-0000(76)80045-1. <a href="https://doi.org/10.1016%2FS0022-0000%2876%2980045-1" target="_blank">https://doi.org/10.1016%2FS0022-0000%2876%2980045-1</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Shih, Wei-Kuan; Hsu, Wen-Lian (1999). "A new planarity test" (PDF). Theoretical Computer Science. 223 (1–2): 179–191. doi:10.1016/S0304-3975(98)00120-0. <a href="https://www.iis.sinica.edu.tw/IASL/webpdf/paper-1999-A_New_Planarity_test.pdf" target="_blank">https://www.iis.sinica.edu.tw/IASL/webpdf/paper-1999-A_New_Planarity_test.pdf</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
</ol>

PQ tree open-in-new

PQ tree