PQ-дерево — структура данных для представления группы перестановок . Это корневое планарное дерево . Висячие вершины в нем представляют переставляемые элементы. Остальные вершины имеют пометку либо ${\displaystyle P}$ , либо ${\displaystyle Q}$ . Вершины с пометкой ${\displaystyle Q}$ имеют по крайней мере 3 потомка, а вершины с пометкой ${\displaystyle P}$ имеют по крайней мере 2 потомка. В PQ-дереве разрешается как угодно переставлять потомков вершины с пометкой ${\displaystyle P}$ и обращать порядок потомков вершины с пометкой ${\displaystyle Q}$ .

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 . — P. 335–379 . — doi : .
• Shih, Wei-Kuan and Hsu, Wen-Lian. (англ.) // Theoretical Computer Science (journal). — 1999. — Vol. 223 . — P. 179–191 . — doi : . 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 .