Editing PQ tree (section)

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