PQ-дерево

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

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

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