PQ-дерево

Граф (a) і його PQ-дерево (b)

PQ-дерево — структура даних для подання групи перестановок, кореневе планарне дерево. Висячі вершини в ньому відповідають подаваним елементам. Решта вершин мають позначку $P$ або $Q$. Вершини з позначкою $Q$ мають принаймні 3 нащадки, а вершини з позначкою $P$ мають принаймні 2 нащадки. У PQ-дереві дозволяється як завгодно переставляти нащадків вершини з позначкою $P$ і обертати порядок нащадків вершини з позначкою $Q$.

PQ-дерево, яке описує вкладений список [1 (2 3 4) 5]

PQ-дерева використовують для пошуку перестановок, обмеження на які стають відомими поступово, одне за іншим. Такі задачі виникають при відтворенні ДНК і перевірці планарності графа.

Статті

• Booth, Kellogg S. and Lueker, George S. Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms // Journal of Computer and System Sciences. — 1976. — Vol. 13, no. 3 (21 April). — P. 335–379. — DOI:10.1016/S0022-0000(76)80045-1.
• Shih, Wei-Kuan and Hsu, Wen-Lian. A new planarity test // Theoretical Computer Science (journal). — 1999. — Vol. 223 (21 April). — P. 179–191. — DOI:10.1016/S0304-3975(98)00120-0. Архівовано з джерела 12 вересня 2006.
• Mehta, D.P. and Sahni, S. 32. PQ Trees, PC Trees, and Planar Graphs // Handbook of Data Structures and Applications. — Taylor & Francis, 2004. — ISBN 9781420035179.
• 3.2. Planarity testing // Planar Graphs: Theory and Algorithms / ed. by T. Nishizeki and N. Chiba. — North-Holland, 1988. — ISBN 0-444-702121.