# Incremental and Interactive PQ-and PC-Trees (Media Exposition)

Simon Fink, Dominik Peters

► To cite this version:

Simon Fink, Dominik Peters. Incremental and Interactive PQ-and PC-Trees (Media Exposition). 41st International Symposium on Computational Geometry (SoCG 2025), CG Society, Jun 2025, Kanazawa, Japan. 10.4230/LIPIcs.SoCG.2025.84 . hal-05367827

HAL Id: hal-05367827

https://hal.science/hal-05367827v1

Submitted on 17 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Incremental and Interactive PQ- and PC-Trees

Simon D. Fink

<figure><img src="image_2.png" /></figure>

Algorithms and Complexity Group, TU Wien, Austria

Dominik Peters

<figure><img src="image_3.png" /></figure>

CNRS, LAMSADE, Université Paris Dauphine – PSL, France

## Abstract

PQ-trees [2,3] (and their more general variant PC-trees [13,17]) are a well-known data structure for representing the set of linear (or for PC-trees, circular) orders respecting a given set of consecutivity constraints. Each such constraint is specified by a set of elements and requires that these elements appear consecutively in the linear (or circular) order; thus, they disallow the set to be interleaved with its complement. The main operation supported by these data structures is thus the so-called *update*, which takes as input a set that forms an additional constraint, and in response changes the tree in order to restrict the represented orders to those satisfying the new constraint. Interpreting a given tree is straightforward: leaves represent the underlying elements, while inner nodes either allow the order of their subtrees to be reversed (Q/C-nodes) or to be arbitrarily permuted (P-nodes). However, the way this structure and the set of represented orders change under updates is less intuitive. We present an interactive web app that allows users to specify sets of consecutivity constraints in the form of a 0/1-matrix and then calculates and visualizes the corresponding PQ- or PC-tree. The constraints can then be changed dynamically while observing how this changes the structure of the tree and the set of represented orders. Through this interactive exploration, we hope to make PQ- and PC-trees more accessible to a wider audience.

**2012 ACM Subject Classification** Human-centered computing → Graphical user interfaces; Mathematics of computing → Permutations and combinations; Applied computing → Interactive learning environments; Theory of computation → Computational geometry

**Keywords and phrases** PQ trees, PC trees, planarity, consecutive ones problem, interactive exploration

**Digital Object Identifier** 10.4230/LIPIcs.SoCG.2025.84

**Category** Media Exposition

**Supplementary Material** InteractiveResource (Website): https://n-coder.github.io/pqtree.js
Software (Source Code): https://github.com/N-Coder/pqtree.js
archived at swh:1:dir:711cf71799908f0a3e15dadcdd93f0499d88cd1a

**Funding** Simon D. Fink: Vienna Science and Technology Fund (WWTF) [10.47379/ICT22029].

## 1 Background

PQ- and PC-trees have applications in many graph drawing problems related to planarity [3, 17] and its variants, such as Level Planarity [6] and Cluster Planarity [9], as well as other layout problems such as NodeTrix [15] or the geometric Segment Intersection Representation problem [11]. More broadly, they are also used for solving variants of the Travelling Salesperson Problem [4], in Computational Biology (such as for Genome Ordering [14]) and to solve the Consecutive Ones Problem on 0/1-matrices [3,13], which has many applications, for example in the analysis of preferences in Computational Social Choice [8].

A *PQ-tree T* is a rooted tree that represents a set of linear orders on some ground set *X* [2,3]. The leaves of *T* are exactly the elements of *X*, while its inner nodes are labelled as either *P-node* or *Q-node*; see Figure 1(b). A *P-node* allows arbitrarily permuting its incident subtrees, while a *Q-node* comes with a fixed order of its incident subtrees that may

<figure><img src="image_4.png" /></figure>

© Simon D. Fink and Dominik Peters;
licensed under Creative Commons License CC-BY 4.0

41st International Symposium on Computational Geometry (SoCG 2025).

Editors: Oswin Aichholzer and Haitao Wang; Article No. 84; pp. 84:1–84:4

Leibniz International Proceedings in Informatics

<figure><img src="image_5.png" /></figure>

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_6.png" /></figure>
<figure><img src="image_7.png" /><figcaption>■ **Figure 1 (a)** A binary matrix representing the elements $X = \{a, b, c, d, e, f, g\}$ as its columns and the three consecutivity restrictions $\{c, e\}, \{b, c, e\}, \{b, c, d, f\}$ through its three rows. (b) A PQ-tree representing all linear orders satisfying the restrictions from (a). (c) A PC-tree representing all circular orders satisfying the restrictions from (a). Images generated by the portfolio website.</figcaption></figure>

only be reversed. All orders of leaves obtained by making these changes at the inner nodes are the linear orders *represented* by the PQ-tree *T*. Similarly, a PC-tree *T* is an unrooted tree that represents a set of circular orders on some ground set *X* [13, 17]. In addition to being unrooted, its only further difference to a PQ-tree is that Q-nodes are called *C-nodes*, but otherwise behave the same in only allowing their fixed order or the reversal thereof; see Figure 1(c). As there is no designated root, the leaf orders obtained from a PC-tree can be circularly shifted, yielding circular instead of linear orders. It has been shown that still, both kinds of trees are actually linear-time equivalent [12].

A *trivial* PQ- or PC-tree consists only of a single inner P-node and represents all permutations of its leaves *X*. Any tree can be obtained from the trivial one by applying a sequence of *update* operations to it. Each update takes as input a subset *A* ⊂ *X* and changes the tree such that the represented orders are restricted to those in which *A* is consecutive. If there are no represented orders where *A* is consecutive, the *null-tree* representing an empty set of orders is returned. The update operation can be implemented to run in $O(|A|)$ time [2,17], although (as we discuss at the end of this paper) this algorithm is far from trivial to implement or explain [1, 7, 10].

In this way, consecutivity restrictions are represented as a family of subsets of *X*. This family can be represented as a binary 0/1 matrix, where each column corresponds to an element of *X*, and each consecutivity restriction corresponds to a row in the matrix, requiring exactly its 1-entries to be consecutive; see Figure 1(a). Note that the problem of finding orders satisfying all consecutivity constraints can now be seen as reordering the columns of the matrix such that all ones are (circularly) consecutive, which is also known as the (Circularly) Consecutive Ones Problem [3, 13].

## 2 Our Portfolio

We use the matrix representation in our portfolio to allow interactively specifying constraints. After the user changes the matrix, the PQ- or PC-tree displayed next to it is automatically updated to represent the desired orders. The columns of the matrix can be reordered manually through drag and drop, or automatically on clicking a button, such that the matrix has the (Circularly) Consecutive Ones Property. Additionally, the website displays how many admissible orders there are and also provides an explicit enumeration of them. In case of a no-instance (where no order satisfies the consecutivity restrictions), we highlight the first restriction that would yield a null-tree, and display the tree obtained from the
restrictions up to right before that point. This makes it easy to verify which elements of
the next restriction cannot be made consecutive. A guided tour further provides a tutorial
explaining the PQ- and PC-tree data structures and how the website can be used. Allowing
to interactively explore PQ- and PC-trees and their relationship to consecutivity-constrained
orders, we hope to make this data structure more accessible to a wider audience. We also
provide visually-pleasing automatic visualizations that can, e.g., easily used for scientific
work building on these structures; see Figure 1.

For PQ-trees, we use a simple top-down tree layout, while the layout of the circular and unrooted PC-trees is slightly more involved. Here, we use a Tutte drawing [16], fixing the leaves in an order admissible by the tree on a circle and then using the force-based approach to draw the inner nodes within the circle. Chiu, Eppstein and Goodrich suggested to assign weights to edges to further improve the aesthetics of Tutte drawings [5]. They use the formula $a/r^i$, where *a* is some scaling constant, *r* is the weighting parameter, and *i* is the minimum distance of the edge to a leaf. As the scaling is applied linearly to all weights and thus does not influence the resulting drawing, we set *a* = 1 in our implementation and only allow the user to tune the *r* value to their liking. Interestingly, while the authors suggested *r* values of 3 and 5 in their paper [5], we find values of 1 or slightly below to better suit the (rather small) graphs we draw.

Future improvements to the website could also allow interactively changing the displayed order right within the currently visualized tree according to the P- and Q/C-node rules. Furthermore, an interactive tour through the individual steps used to update a PQ- or PC-tree could further help in understanding this algorithm. Note that the update of PQ-trees is through a rather involved recursive matching and application of 9 different “templates” [2], resulting in an algorithm that is famously hard to implement correctly [7, 10]. The update on PC-trees streamlines this to an update in one go, although its correct linear-time implementation is still rather challenging [1, 10]. Thus, some trade-offs for simplicity of explanation will need to be made when interactively executing these algorithms, as is e.g. also done by the static explanation of the update we currently link to [1].

References

1 Rami Benelmir, Christoph Dürr, Erisa Kohansal, and Yanni Lefki. PC Trees, January 2024.
URL: https://tryalgo.org/en/data%20structures/2024/01/03/pc-trees/.

2 Kellogg S. Booth. *PQ-tree algorithms*. PhD thesis, University of California, Berkeley, 1975.

3 Kellogg S. Booth and George S. Lueker. 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, 1976. doi:10.1016/S0022-0000(76)80045-1.

4 Rainer E. Burkard, Vladimir G. Deňeko, and Gerhard J. Woeginger. The Travelling Salesman and the PQ-Tree. *Mathematics of Operations Research*, 23(3):613-623, 1998. Publisher: INFORMS. doi:10.1287/MOOR.23.3.613.

5 Alvin Chiu, David Eppstein, and Michael T. Goodrich. Manipulating Weights to Improve Stress-Graph Drawings of 3-Connected Planar Graphs. In Michael A. Bekos and Markus Chimani, editors, *Graph Drawing and Network Visualization*, pages 141–149, Cham, 2023. Springer Nature Switzerland. doi:10.1007/978-3-031-49275-4_10.

6 G. Di Battista and E. Nardelli. Hierarchies and planarity theory. *IEEE Transactions on Systems, Man, and Cybernetics*, 18(6):1035–1046, November 1988. Conference Name: IEEE Transactions on Systems, Man, and Cybernetics. doi:10.1109/21.23105.

7 Christoph Dürr. PQ trees, December 2017. URL: https://tryalgo.org/en/data%20structures/2017/12/15/pq-trees/.
8 Edith Elkind, Martin Lackner, and Dominik Peters. Preference Restrictions in Computational Social Choice: A Survey, May 2022. arXiv:2205.09092 [cs]. doi:10.48550/arXiv.2205.09092.

9 Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. In Gerhard Goos, Juris Hartmanis, Jan Leeuwen, and Paul Spirakis, editors, *Algorithms — ESA '95*, volume 979, pages 213–226. Springer Berlin Heidelberg, Berlin, Heidelberg, 1995. Series Title: Lecture Notes in Computer Science. doi:10.1007/3-540-60313-1_145.

10 Simon D. Fink, Matthias Pfretzschner, and Ignaz Rutter. Experimental Comparison of PC-Trees and PQ-Trees. *ACM J. Exp. Algorithmics*, 28:1.10:1–24, 2023. Publisher: Association for Computing Machinery (ACM). doi:10.1145/3611653.

11 Simon D. Fink, Matthias Pfretzschner, and Peter Stumpf. Segment Intersection Representations, Level Planarity and Constrained Ordering Problems, February 2025. arXiv:2502.16621 [cs]. doi:10.48550/arXiv.2502.16621.

12 Bernhard Haeupler and Robert E. Tarjan. Planarity Algorithms via PQ-Trees (Extended Abstract). *Electronic Notes in Discrete Mathematics*, 31:143–149, August 2008. doi:10.1016/j.endm.2008.06.029.

13 Wen-Lian Hsu and Ross M. McConnell. PC trees and circular-ones arrangements. *Theoretical Computer Science*, 296(1):99–116, March 2003. doi:10.1016/S0304-3975(02)00435-8.

14 Gad M. Landau, Laxmi Parida, and Oren Weimann. Using PQ trees for comparative genomics. *Lecture Notes in Computer Science*, 3537:128–143, 2005. doi:10.1007/11496656_12.

15 Giuseppe Liotta, Ignaz Rutter, and Alessandra Tappini. Simultaneous FPQ-ordering and hybrid planarity testing. *Theoretical Computer Science*, 874:59–79, June 2021. doi:10.1016/j.tcs.2021.05.012.

16 W. T. Tutte. How to Draw a Graph. *Proceedings of the London Mathematical Society*, s3-13(1):743–767, 1963. doi:10.1112/plms/s3-13.1.743.

17 Shih Wei-Kuan and Hsu Wen-Lian. A new planarity test. *Theoretical Computer Science*, 223(1):179–191, July 1999. doi:10.1016/S0304-3975(98)00120-0.