Incremental and Interactive PQ- and PC-Trees

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 the 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 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\subset 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 [10, 7, 1].

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

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 [10, 7]. The update on PC-trees streamlines this to an update in one go, although its correct linear-time implementation is still rather challenging [10, 1]. 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].