Faculty of Informatics and Mathematics, University of Passau,
Germanyfinksim@fim.uni-passau.dehttps://orcid.org/0000-0002-2754-1195DFG-grant
Ru-1903/3-1 Faculty of Informatics and Mathematics, University of Passau,
Germanypfretzschner@fim.uni-passau.dehttps://orcid.org/0000-0002-5378-1694DFG-
grant Ru-1903/3-1 Faculty of Informatics and Mathematics, University of
Passau<EMAIL_ADDRESS>passau.dehttps://orcid.org/0000-0002-3794-4406DFG-grant Ru-1903/3-1 Simon D.
Fink and Matthias Pfretzschner and Ignaz Rutter [500]Mathematics of computing
Permutations and combinations [500]Mathematics of computing Trees
[500]Mathematics of computing Graph algorithms https://github.com/N-Coder/pc-
tree/ Work partially supported by DFG-grant Ru-1903/3-1. John Q. Open and Joan
R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016
CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23 Om

(a) #1

# Experimental Comparison of PC-Trees and PQ-Trees

Simon D. Fink  Matthias Pfretzschner  Ignaz Rutter

###### Abstract

PQ-trees and PC-trees are data structures that represent sets of linear and
circular orders, respectively, subject to constraints that specific subsets of
elements have to be consecutive. While equivalent to each other, PC-trees are
conceptually much simpler than PQ-trees; updating a PC-trees so that a set of
elements becomes consecutive requires only a single operation, whereas PQ-
trees use an update procedure that is described in terms of nine
transformation templates that have to be recursively matched and applied.

Despite these theoretical advantages, to date no practical PC-tree
implementation is available. This might be due to the original description by
Hsu and McConnell [14] in some places only sketching the details of the
implementation. In this paper, we describe two alternative implementations of
PC-trees. For the first one, we follow the approach by Hsu and McConnell,
filling in the necessary details and also proposing improvements on the
original algorithm. For the second one, we use a different technique for
efficiently representing the tree using a Union-Find data structure. In an
extensive experimental evaluation we compare our implementations to a variety
of other implementations of PQ-trees that are available on the web as part of
academic and other software libraries. Our results show that both PC-tree
implementations beat their closest fully correct competitor, the PQ-tree
implementation from the OGDF library [6, 15], by a factor of 2 to 4, showing
that PC-trees are not only conceptually simpler but also fast in practice.
Moreover, we find the Union-Find-based implementation, while having a slightly
worse asymptotic runtime, to be twice as fast as the one based on the
description by Hsu and McConnell.

###### keywords:

PQ-Tree, PC-Tree, circular consecutive ones, implementation, experimental
evaluation

##  1 Introduction

PQ-trees represent linear orders of a ground set subject to constraints that
require specific subsets of elements to be consecutive. Similarly, PC-trees do
the same for circular orders subject to consecutivity constraints. PQ-trees
were developed by Booth and Lueker [3] to solve the consecutive ones problem,
which asks whether the columns of a Boolean matrix can be permuted such that
the 1s in each row are consecutive. PC-trees are a more recent generalization
introduced by Shih and Hsu [16] to solve the circular consecutive ones
problem, where the 1s in each row only have to be circularly consecutive.

Though PQ-trees represent linear orders and PC-trees represent circular
orders, Haeupler and Tarjan [10] show that in fact PC-trees and PQ-trees are
equivalent, i.e., one can use one of them to implement the other without
affecting the asymptotic running time. The main difference between PQ-trees
and PC-trees lies in the update procedure. The update procedure takes as input
a PQ-tree (a PC-tree) $T$ and a subset $U$ of its leaves and produces a new
PQ-tree (PC-tree) $T^{\prime}$ that represents exactly the linear orders
(circular orders) represented by $T$ where the leaves in $U$ appear
consecutively. The update procedure for PC-trees consists only of a single
operation that is applied independently of the structure of the tree. In
contrast, the update of the PQ-tree is described in terms of a set of nine
template transformations that have to be recursively matched and applied.

PQ-trees have numerous applications, e.g., in planarity testing [3, 16],
recognition of interval graphs [3] and genome sequencing [1]. Nevertheless,
PC-trees have been adopted more widely, e.g., for constrained planarity
testing problems [2, 5] due to their simpler update procedure. Despite their
wide applications and frequent use in theoretical algorithms, few PQ-tree
implementations and even fewer PC-tree implementations are available. Table 1
shows an overview of all PC/PQ-tree implementations that we are aware of,
though not all of them are working.

In this paper we describe the first correct and generic implementations of PC-
trees. Section 2 contains an overview of the update procedure for applying a
new restriction to a PC-tree. In Section 3, we describe the main challenge
when implementing PC-trees and how our two implementations take different
approaches at solving it. In Section 4, we present an extensive experimental
evaluation, where we compare the performance of our implementations with the
implementations of PC-trees and PQ-trees from Table 1. Our experiments show
that, concerning running time, PC-trees following Hsu and McConnell’s original
approach beat their closest competitor, the PQ-tree implementation from the
OGDF library [6] by roughly a factor 2. Our second implementation using Union-
Find is another 50% faster than this first one, thus beating the OGDF
implementation by a factor of up to 4.

##  2 The PC-tree

A _PC-tree_ $T$ is a tree without degree-2 vertices whose inner nodes are
partitioned into _P-nodes_ and _C-nodes_. Edges incident to C-nodes have a
circular order that is fixed up to reversal, whereas edges incident to P-nodes
can be reordered arbitrarily. Traversing the tree according to fixed orders
around the inner nodes determines a circular ordering of the leaves $L$ of the
tree. Any circular permutation of $L$ that can be obtained from $T$ after
arbitrarily reordering the edges around P-nodes and reversing orders around
C-nodes is a _valid permutation_ of $L$. In this way a PC-tree represents a
set of circular permutations of $L$.

When applying a _restriction_ $R\subseteq L$ to $T$, we seek a new tree that
represents exactly the valid permutations of $L$ where the leaves in $R$
appear consecutively. We call a restriction _impossible_ if there is no valid
permutation of $L$ where the leaves in $R$ are consecutive. Thus, restriction
$R$ is possible if and only if the edges incident to P-nodes can be rearranged
and orders of edges incident to C-nodes can be reversed in such a way that all
leaves in $R$ are consecutive. Updating a PC-tree to enforce the new
restriction can thus be done by identifying and adapting the nodes that decide
about the consecutivity of the elements of $R$ and then changing the tree to
ensure that this consecutivity can no longer be broken.

Let a leaf $x\in L$ be _full_ if $x\in R$ and _empty_ otherwise. We call an
edge _terminal_ if the two subtrees separated by the edge both contain at
least one empty and at least one full leaf. Exactly the endpoints of all
terminal edges need to be “synchronized” to ensure that all full leaves are
consecutive. Hsu and McConnell [14, 13] show that $R$ is possible if and only
if the terminal edges form a path and all nodes of this path can be flipped so
that all full leaves are on one side and all empty leaves are on the other.
This path is called the _terminal path_ , the two nodes at the ends of the
terminal path are the _terminal nodes_. Observe that each node in $T$ that is
adjacent to two subtrees of which one only contains full leaves and the other
contains only empty leaves is contained in the terminal path. Figure 1(b)
illustrates the terminal path.

(b)

(c)

Figure 1:  (a) Two equivalent PC-Trees with their nodes colored according to
the restriction $\\{4,8,10,11,12,15\\}$. C-nodes are represented by big double
circles and the P-nodes are represented by small circles. The white nodes
represent empty nodes, the black nodes represent full nodes and the gray nodes
represent partial nodes. The thick edges represent the terminal path with
terminal nodes $t_{1}$ and $t_{2}$. As the restriction is possible, all full
leaves of the tree on the left can be made consecutive, as shown on the right.
Furthermore all nodes that must be modified lie on a path.
(b) Updated PC-tree with new central C-node $c$.

When updating $T$ in order to apply the restriction, every node on the
terminal path is split into two nodes, one of which holds all edges to
neighbors of the original node whose subtree has only full leaves, the other
holds all edges to empty neighbors, while terminal edges are deleted. A new
central C-node $c$ is created that is adjacent to all the split nodes in such
a way that it preserves the order of the neighbors around the terminal path.
Contracting all edges to the split C-nodes incident to $c$ and contracting all
nodes with degree two results in the updated tree that represents the new
restriction [14, 13]. 1 shows an example of this update, while Figure 2
details changes made to the terminal path.

Figure 2:  Left: The terminal path with all full subtrees shown in black on
top and all empty subtrees shown in white on the bottom. Middle: The updated
PC-tree, where all terminal edges were deleted, all nodes on the terminal were
split in a full and empty half and all new nodes were connected to a new
C-node $c$. Right: The PC-Tree after contracting all new C-nodes and all
degree-2 P-nodes into $c$.

It remains to efficiently find the terminal edges, and thus the subtrees with
mixed full and empty leaves. To do so, Hsu and McConnell first choose an
arbitrary node of the tree as root. They also assign labels to the inner nodes
of the tree, marking an inner node (and conceptually the subtree below it)
_partial_ if at least one of its neighbors (i.e. children or parent) is full,
_full_ if all its neighbors except one (which usually is the parent) are full,
and _empty_ otherwise. Then, an edge is terminal if and only if it lies on a
path between two partial nodes [14, 13]. Assigning the labels and subsequently
finding the terminal edges can be done by two bottom-up traversals of the
tree. We summarize these steps in the following, more fine-granular
description of Hsu and McConnell’s algorithm for updating the PC-tree [13,
Algorithm 32.2]:

#### Algorithm for Applying Restrictions.

To add a new restriction $R$ to a PC-tree $T$:

  1. 1.

Label all partial and full nodes by searching the tree bottom-up from all full
leaves.

  2. 2.

Find the terminal path by walking the tree upwards from all partial nodes in
parallel.

  3. 3.

Perform flips of C-nodes and modify the cyclic order of edges incident to
P-nodes so that all full leaves lie on one side of the path.

  4. 4.

Split each node on the path into two nodes, one incident to all edges to full
leaves and one incident to all edges to empty leaves.

  5. 5.

Delete the edges of the path and replace them with a new C-node $c$, adjacent
to all split nodes, whose cyclic order preserves the order of the nodes on
this path.

  6. 6.

Contract all edges from $c$ to adjacent C-nodes, and contract any node that
has only two neighbors.

##  3 Our Implementations

The main challenge posed to the data structure for representing the PC-tree is
that, in Item 6, it needs to be able to merge arbitrarily large C-nodes in
constant time for the overall algorithm to run in linear time. This means
that, whenever C-nodes are merged, updating the pointer to a persistent C-node
object on every incident edge would be too expensive. Hsu and McConnell (see
[13, Definition 32.1]) solve this problem by using C-nodes that, instead of
having a permanent node object, are only represented by the doubly-linked list
of their incident half-edges, which we call _arcs_. This complicates various
details of the implementation, like finding the parent pointer of a C-node,
which are only superficially covered in the initial work of Hsu and McConnell
[14]. These issues are in part remedied by the so called _block-spanning
pointers_ introduced in the later published book chapter [13], which are
related to the pointer borrowing strategy introduced by Booth and Lueker [3].
These block-spanning pointers link the first and last arc of a consecutive
block of full arcs (i.e. the arcs to full neighbors) around a C-node and can
be accompanied by temporary C-node objects, see the blue dashed arcs in
Figures 13(c), 13(d) and 11 in the Appendix for an example. Whenever a
neighbor of a C-node becomes full, either a new block is created for the
corresponding arc of the C-node (Figure 11(a) left), an adjacent block grows
by one arc (Figure 11(a) right), or the two blocks that now became adjacent
are merged (Figure 11(b)).

Using this data structure, Hsu and McConnell show that the addition of a
single new restriction $R$ takes $O(p+|R|)$ time, where $p$ is the length of
the terminal path, and that applying restrictions $R_{1},\ldots,R_{k}$ takes
$\Theta(|L|+\sum_{i=1}^{k}|R_{i}|)$ time [14, 13]. Especially for Items 1 and
2, they only sketch the details of the implementation, making it hard to
directly put it into practice. In Appendix B, we fill in the necessary details
for these steps and also refine their runtime analysis, showing that Item 1
can be done in $O(|R|)$ time and Item 2 can be done in $O(p)$ time. Using the
original procedures by Hsu and McConnell, Items 3 and 4 can be done in
$O(|R|)$ time and Items 5 and 6 can be done in $O(p)$ time.

For our first implementation, which we call HsuPC, we directly implemented
these steps in C++, using the data structure without permanent C-node objects
as described by Hsu and McConnell. During the evaluation, we realized that
traversals of the tree are expensive. This is plausible, as they involve a lot
of pointer-dereferencing to memory segments that are not necessarily close-by,
leading to cache misses. To avoid additional traversals for clean-up purposes,
we store information that is valid only during the update procedure with a
timestamp. Furthermore, we found that keeping separate objects for arcs and
nodes and the steps needed to work around the missing C-node objects pose a
non-negligible overhead.

To remove this overhead, we created a second version of our implementation,
which we call UFPC, using a Union-Find tree for representing C-node objects:
Every C-node is represented by an entry in the Union-Find tree and every
incident child edge stores a reference to this entry. Whenever two C-nodes are
merged, we apply union to both entries and only keep the object of the entry
that survives. This leads to every lookup of a parent C-node object taking
amortized $O(\alpha(|L|))$ time, where $\alpha$ is the inverse Ackermann
function. Although this makes the overall runtime super-linear, the
experimental evaluation following in the next section shows that this actually
improves the performance in practice. As a second change, the UFPC no longer
requires separate arc and node objects, allowing us to use a doubly-linked
tree consisting entirely of nodes that store pointers to their parent node,
left and right sibling node, and first and last child node. Edges are
represented implicitly by the child node whose parent is the other end of the
edge. Note that of the five stored pointers, a lookup in the Union-Find data
structure is only needed for resolving the parent of a node.

In Appendix B, we describe our algorithmic improvements and differences of
both implementations. We use the Union-Find data structure from the OGDF [6]
and plan to merge our UFPC implementation into the OGDF. Furthermore, both
implementations should also be usable stand-alone with a custom Union-Find
implementation. The source code for both implementations, our evaluation
harness and all test data are available on GitHub (see Table 1).

##  4 Evaluation

In this section, we experimentally evaluate our PC-tree implementations by
comparing the running time for applying a restriction with that of various PQ-
and PC-tree implementations that are publicly available. In the following we
describe our method for generating test cases, our experimental setup and
report our results.

###  4.1 Test Data Generation

To generate PQ-trees and restrictions on them, we make use of the planarity
test by Booth and Lueker [3], one of the initial applications of PQ-trees.
This test incrementally processes vertices one by one according to an
$st$-ordering. Running the planarity test on a graph with $n$ vertices applies
$n-1$ restrictions to PQ-trees of various sizes. Since not all implementations
provide the additional modification operations necessary to implement the
planarity test, we rather export, for each step of the planarity test, the
current PQ-tree and the restriction that is applied to it as one instance of
our test set. We note that the use of $st$-orderings ensures that the
instances do not require the ability of the PC-tree to represent circular
permutations, making them good test cases for comparing PC-trees and PQ-trees.

In this way, we create one test set SER-POS consisting of only PQ-trees with
possible restrictions by exporting the instances from running the planarity
test on a randomly generated biconnected planar graph for each vertex count
$n$ from $1000$ to $20,000$ in steps of $1000$ and each edge count
$m\in\\{2n,3n-6\\}$. To avoid clutter, to remedy the tendency of the planarity
test to produce restrictions with very few leaves, and to avoid bias from
trivial optimizations such as filtering trivial restrictions with
$|R|\in\\{1,|L|-1,|L|\\}$, which is present in some of the implementations, we
filter test instances where $|R|$ lies outside the interval $[5,|L|-2]$.
Altogether, this test set contains $199,831$ instances, whose distribution
with regards to tree and restriction size is shown in
LABEL:fig:distplot_full_leaves_tree_size_possible.

To guard against overly permissive implementations, we also create a small
test set SER-IMP of impossible restrictions. It is generated in the same way,
by adding randomly chosen edges to the graphs from above until they become
non-planar. In this case the planarity test fails with an impossible
restriction at some point; we include these $3,800$ impossible restrictions in
the set, see LABEL:fig:distplot_full_leaves_tree_size_impossible.

As most of the available implementations have no simple means to store and
load a PQ-/PC-tree, we serialize each test instance as a set of restrictions
that create the tree, together with the additional new restriction. When
running a test case, we then first apply all the restrictions to reobtain the
tree, and then measure the time to apply the new restriction from the test
case. The prefix SER- in the name of both sets emphasizes this serialization.

To be able to conduct a more detailed comparison of the most promising
implementations, we also generate a third test set with much larger instances.
As deserializing a PC- or PQ-tree is very time-consuming, we directly use the
respective implementations in the planarity test by Booth and Lueker [3], thus
calling the set DIR-PLAN. We generated 10 random planar graphs with $n$
vertices and $m$ edges for each $n$ ranging from $100,000$ to $1,000,000$ in
steps of $100,000$ and each $m\in\\{2n,3n-6\\}$, yielding 200 graphs in total.
The planarity test then yields one possible restriction per node. As we only
want to test big restrictions, we filter out restrictions with less than 25
full leaves, resulting in DIR-PLAN containing $564,300$ instances.

distplot_full_leaves_tree_size_possible
distplot_full_leaves_tree_size_impossible

Figure 3:  Distribution of tree and restriction size for the data sets (a)
SER-POS and (b) SER-IMP. Please note the different color scales. The SER-POS
instances that are left of the black line are too small and filtered out.

###  4.2 Experimental Setup

Name | Type | Context | Language | Correct | Errors |  URL
---|---|---|---|---|---|---
HsuPC | PC-Tree | our impl., based on [13] | C++ | ✓ | 0 |  https://github.com/N-Coder/pc-tree/tree/HsuPCSubmodule
UFPC | PC-Tree | our impl. using Union-Find | C++ | ✓ | 0 |  https://github.com/N-Coder/pc-tree
Luk&Zhou | PC-Tree | student course project | C++ | $-$ | $-$ |  https://github.com/kwmichaelluk/pc-tree
Hsu [12] | PC-Tree | planarity test prototype | C++ | n.a. | $-$ |  http://qa.iis.sinica.edu.tw/graphtheory
Noma [4] | PC-Tree | planarity test evaluation | C++ | n.a. | $-$ |  https://www.ime.usp.br/~noma/sh
OGDF [15] | PQ-Tree | planarity testing | C++ | ✓ | 0 |  https://ogdf.github.io
Gregable | PQ-Tree | biclustering | C++ | ✓ | 0 |  https://gregable.com/2008/11/pq-tree-algorithm.html
BiVoC [9] | PQ-Tree | automatic layout of biclusters | C++ | ✗ | 71 |  https://bioinformatics.cs.vt.edu/~murali/papers/BiVoC
Reisle | PQ-Tree | student project | C++ | ✗ | 236 |  https://github.com/creisle/pq-trees
GraphSet [8] | PQ-Tree | visual graph editor | C++ | ✗ | 580 |  http://graphset.cs.arizona.edu
Zanetti [17] | PQR-Tree11footnotemark: 1 | extension of PQ-Trees | Java | ✗ | 454 |  https://github.com/jppzanetti/PQRTree
CppZanetti | PQR-Tree11footnotemark: 1 | our C++ conversion of Zanetti | C++ | ✗ | 454 |  https://github.com/N-Coder/pc-tree#installation
JGraphEd [11] | PQ-Tree | visual graph editor | Java | ✗ | 11 |  https://www3.cs.stonybrook.edu/~algorith/implement/jgraphed/implement.shtml
GTea [7] | PQ-Tree | visual graph theory tool | Java | $-$ | $-$ |  https://github.com/rostam/GTea
TryAlgo | PQ-Tree | consecutive-ones testing | Python | $-$ | $-$ |  https://tryalgo.org/en/datastructures/2017/12/15/pq-trees
SageMath | PQ-Tree | interval graph detection | Python | ✓ | 0 |  https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/pq_trees.html

Table 1:  Implementations considered for the evaluation. Implementations that
are entirely unusable as they are incomplete or crash/produce incorrect
results on almost all inputs (marked with $-$) and those where no stand-alone
PC-/PQ-tree implementation could be extracted (marked with n.a.) could not be
evaluated. Correct implementations are marked with ✓and implementations that
are functional, but do not always produce correct results are marked with ✗.
These two categories are included in our experimental evaluation. The last
column shows how many of $203,630$ restrictions in the sets SER-POS and SER-
IMP failed.

11footnotemark: 1

PQR-Trees are a variant of PQ-Trees that can also represent impossible
restrictions, replacing any node that would make a restriction impossible by
an R-node (again allowing arbitrary permutation). To make the implementations
comparable, we abort early whenever an impossible restriction is detected and
an R-node would be generated.

Table 1 gives an overview of all implementations we are aware of, although not
all implementations could be considered for the evaluation.

The three existing implementations of PC-trees we found are incomplete and
unusable (Luk&Zhou) or tightly intertwined with a planarity test in such a way
that we were not able to extract a generic implementation of PC-trees (Hsu,
Noma). We further exclude two PQ-tree implementations as they either crash or
produce incorrect results on almost all inputs (GTea) or have an excessively
poor running time (TryAlgo). Among the remaining PQ-tree implementations only
three correctly handle all our test cases (OGDF, Gregable, SageMath). Several
other implementations have smaller correctness issues: After applying a fix to
prevent segmentation faults in a large number of cases for BiVoC, the
remaining implementations crash (BiVoC, GraphSet, Zanetti) and/or produce
incorrect results (Reisle, JGraphEd, Zanetti) on a small fraction of our
tests; compare the last column of Table 1. We nevertheless include them in our
evaluation.

We changed the data structure responsible for mapping the input to the leaves
of the tree for BiVoC and Gregable from std::map to std::vector to make them
competitive. Moreover, BiVoC, Gregable and GraphSet use a rather expensive
cleanup step that has to be executed after each update operation. As this
could probably largely be avoided by the use of timestamps, we do not include
the cleanup time in their reported running times. For SageMath the initial
implementation turned out to be quadratic, which we improved to linear by
removing unnecessary recursion. As Zanetti turned out to be a close competitor
to our implementation in terms of running time, we converted the original Java
implementation to C++ to allow a fair comparison. This decreased the runtime
by one third while still producing the exact same results. All other non-C++
implementations were much slower or had other issues, making a direct
comparison of their running times within the same language environment as our
implementations unnecessary. Further details on the implementations can be
found in Appendix A.

Each experiment was run on a single core of a Intel Xeon E5-2690v2 CPU (3.00
GHz, 10 Cores) with 64 GiB of RAM, running Linux Kernel version 4.19.
Implementations in C++ were compiled with GCC 8.3.0 and optimization -O3
-march=native -mtune=native. Java implementations were executed on OpenJDK
64-Bit Server VM 11.0.9.1 and Python implementations were run with CPython
3.7.3. For the Java implementations we ran each experiment several times, only
measuring the last one to remove startup-effects and to facilitate
optimization by the JIT compiler. We used OGDF version 2020.02 (Catalpa) to
generate the test graphs.

###  4.3 Results

relplot_time_full_leaves_possible relplot_time_tree_size_possible

Figure 4: Runtime for SER-POS restrictions depending on (a) restriction size
and (b) tree size.

heatmap_time_possible_buckets relplot_time_tp_length_possible

Figure 5:  (a) A heatmap showing the average runtime of SER-POS restrictions,
depending on both the size of the restriction and the size of the tree. The
color scale is based on the maximum runtime of each respective implementation.
(b) Runtime for SER-POS restrictions depending on the terminal path length.

relplot_time_full_leaves_impossible relplot_time_tree_size_impossible

Figure 6:  Runtime for SER-IMP restrictions depending on (a) restriction size
and (b) tree size for all implementations.

Our experiments turn out that SageMath, even with the improvements mentioned
above, is on average 30 to 100 times slower than all other
implementations.222Part of this might be due to the overhead of running the
code with CPython. As the following analysis shows, SageMath also has other
issues, allowing us to safely exclude it. For the sake of readability, we
scale our plots to focus on the other implementations. As the main application
of PC-/PQ-trees is applying possible restrictions, we first evaluate on the
dataset SER-POS. Figure 4 shows the runtime for individual restrictions based
on the size of the restriction (i.e. the number of full leaves) and the
overall size of the tree. LABEL:fig:relplot_time_full_leaves_possible clearly
shows that for all implementations the runtime is linear in the size of the
restriction. LABEL:fig:relplot_time_tree_size_possible suggests that the
runtime of Reisle and GraphSet does not solely depend on the restriction size,
but also on the size of the tree. To verify this, we created for each
implementation a heatmap that indicates the average runtime depending on both
the tree size and the restriction size, shown in
LABEL:fig:heatmap_time_possible_buckets. The diagonal pattern shown by
SageMath, Reisle, and GraphSet confirms the dependency on the tree size. All
other implementations exhibit vertical stripes, which shows that their runtime
does not depend on the tree size. Finally,
LABEL:fig:relplot_time_tp_length_possible shows the runtime compared to the
terminal path length. As expected, all implementations show a linear
dependency on the terminal path length, with comparable results to
LABEL:fig:relplot_time_full_leaves_possible.

Figure 6 shows the performance on the dataset SER-IMP. The performance is
comparable with that on SER-POS. Noteworthy is that Zanetti performs quite a
bit worse, which is due to its implementation not being able to detect failure
during a labeling step. It always performs updates until a so-called R-node
would be generated. Altogether, the data from SER-POS and SER-IMP shows that
the implementations GraphSet, OGDF, Zanetti, HsuPC and UFPC are clearly
superior to the others. In the following, we conduct a more detailed
comparison of these implementations by integrating them into a planarity test
and running them on much larger instances, i.e., the data set DIR-PLAN. In
addition to an update method, this requires a method for replacing the now-
consecutive leaves by a P-node with a given number of child leaves. Adding the
necessary functionality would be a major effort for most of the
implementations, which is why we only adapted the most efficient
implementations to run this set. We also exclude GraphSet from this
experiment; the fact that it scales linearly with the tree size causes the
planarity test to run in quadratic time (see also Appendix A). Figure 7 again
shows the runtime of individual restrictions depending on the restriction
size. Curiously, Zanetti produces incorrect results for nearly all graphs with
$m=2n$ in LABEL:fig:planaritytest_scatter_size_2n. As the initial tests
already showed, the implementation has multiple flaws; one major issue is
already described in an issue on GitHub, while we give a small example of
another independent error in Figure 10 in the appendix. Both plots show that
HsuPC is more than twice as fast as OGDF and that UFPC is again close to two
times faster than HsuPC. Zanetti’s runtime is roughly the same as that of
HsuPC, while converting its Java code to C++ brings the runtime down close to
that of UFPC.

As OGDF is the slowest, we use it as baseline to calculate the speedup of the
other implementations. LABEL:fig:planaritytest_speedup_size shows that the
runtime improvement for all three implementations is the smallest for small
restrictions, quickly increasing to the final values of roughly $0.4$ times
the runtime of OGDF for HsuPC and $0.25$ for both CppZanetti and UFPC.
LABEL:fig:planaritytest_speedup_tp_length shows the speedup depending on the
length of the terminal path. For very short terminal paths (which are common
in our datasets, see Figure 9 in the appendix), both implementations are again
close; but already for slightly longer terminal paths UFPC quickly speeds up
to being roughly 20% faster than CppZanetti. This might be because creating
the central node in Item 5 is more complicated for UFPC, as the data structure
without edge objects does not allow arbitrarily adding and removing edges
(which is easier for HsuPC) and allowing circular restrictions forces UFPC to
also pay attention to various special cases (which are not necessary for PQ-
trees).

planaritytest_scatter_size_2n planaritytest_scatter_size_3n

Figure 7:  Runtime of individual restrictions of DIR-PLAN with OGDF, Zanetti
and our implementations for graphs of size (a) $m=2n$ and (b) $m=3n-6$.

planaritytest_speedup_size planaritytest_speedup_tp_length

Figure 8:  Median performance increase depending on (a) the size of the
restriction and (b) the terminal path length, with OGDF as baseline. The
shaded areas show the interquartile range.

##  5 Conclusion

In this paper we have presented the first fully generic and correct
implementations of PC-trees. One implementation follows the original
description of Hsu and McConnell [14, 13], which contains several subtle
mistakes in the description of the labeling and the computation of the
terminal path. This may be the reason why no fully generic implementation has
been available so far. A corrected version that also includes several small
simplifications is given in the appendix.

Furthermore, we provided a second, alternative implementation, using Union-
Find to replace many of the complications of Hsu and McConnell’s original
approach. Technically, this increases the runtime to
$O((|R|+p)\cdot\alpha(|L|))$, where $\alpha$ is the inverse Ackerman function.
In contrast, our evaluations show that the Union-Find-based approach is even
faster in practice, despite the worse asymptotic runtime.

Our experimental evaluation with a variety of other implementations reveals
that surprisingly few of them seem to be fully correct. Only three other
implementation have correctly handled all our test cases. The fastest of them
is the PQ-tree implementation of OGDF, which our Union-Find-based PC-tree
implementation beats by roughly a factor of 4. Interestingly, the Java
implementation of PQR-trees by Zanetti achieves a similar speedup once ported
to C++. However, Zanetti’s Java implementation is far from correct and it is
hard to say whether it is possible to fix it without compromising its
performance.

Altogether, our results show that PC-trees are not only conceptually simpler
than PQ-trees but also perform well in practice, especially when combined with
Union-Find. To put the speedup of factor 4 into context, we compared the OGDF
implementations of the planarity test by Booth and Lueker and the one by Boyer
and Myrvold on our graph instances. The Boyer and Myrvold implementation was
roughly 40% faster than the one by Booth and Lueker. Replacing the PQ-trees,
which are the core part of Booth and Lueker’s algorithm, by an implementation
that is 4 time faster, might make this planarity test run faster than the one
by Boyer and Myrvold. We leave a detailed evaluation, also taking into account
the embedding generation, which our PC-tree based planarity test not yet
provides, for future work.

## References

  * [1] S. Benzer.  On the topology of the genetic fine structure.  Proceedings of the National Academy of Sciences, 45(11):1607–1620, nov 1959.  doi:10.1073/pnas.45.11.1607.
  * [2] Thomas Bläsius and Ignaz Rutter.  Simultaneous PQ-ordering with applications to constrained embedding problems.  ACM Trans. Algorithms, 12(2):16:1–16:46, 2016.  doi:10.1145/2738054.
  * [3] Kellogg S. Booth and George S. Lueker.  Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms.  J. Comput. Syst. Sci., 13(3):335–379, 1976.  doi:10.1016/S0022-0000(76)80045-1.
  * [4] John M. Boyer, Cristina G. Fernandes, Alexandre Noma, and José C. de Pina.  Lempel, Even, and Cederbaum planarity method.  In Experimental and Efficient Algorithms, pages 129–144. Springer Berlin Heidelberg, 2004.  doi:10.1007/978-3-540-24838-5_10.
  * [5] Guido Brückner and Ignaz Rutter.  Partial and constrained level planarity.  In Philip N. Klein, editor, Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17), pages 2000–2011. SIAM, 2017.  doi:10.1137/1.9781611974782.130.
  * [6] Markus Chimani, Carsten Gutwenger, Michael Jünger, Gunnar W. Klau, Karsten Klein, and Petra Mutzel.  The Open Graph Drawing Framework (OGDF), chapter 17.  CRC Press, 2014.
  * [7] Alex William Cregten and Hannes Kristján Hannesson.  Implementation of a planarity testing method using PQ-trees.  Technical report, Reykjavík University, 2017.  URL: https://skemman.is/bitstream/1946/29618/1/Planarity_testing_with_PQTrees.pdf.
  * [8] Alejandro Estrella-Balderrama, J. Joseph Fowler, and Stephen G. Kobourov.  Graph simultaneous embedding tool, GraphSET.  In Graph Drawing, pages 169–180. Springer Berlin Heidelberg, 2009\.  doi:10.1007/978-3-642-00219-9_17.
  * [9] Gregory A. Grothaus, Adeel Mufti, and T. M. Murali.  Automatic layout and visualization of biclusters.  Algorithms for Molecular Biology, 1(1):15, 2006.  doi:10.1186/1748-7188-1-15.
  * [10] Bernhard Haeupler and Robert E. Tarjan.  Planarity algorithms via PQ-trees (extended abstract).  Electronic Notes in Discrete Mathematics, 31:143–149, aug 2008\.  doi:10.1016/j.endm.2008.06.029.
  * [11] Jon Harris.  JGraphEd – a java graph editor and graph drawing framework.  Technical report, Carleton University, School of Computer Science, Comp 5901 Directed Studies, 2004.  URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.188.5066&rank=1.
  * [12] Wen-Lian Hsu.  An efficient implementation of the PC-tree algorithm of Shih & Hsu’s planarity test.  Technical report, Institute of Information Science, Academia Sinica, 2003\.  URL: http://iasl.iis.sinica.edu.tw/webpdf/paper-2003-PLANAR_implementation.pdf.
  * [13] Wen-Lian Hsu and Ross McConnell.  PQ trees, PC trees, and planar graphs.  In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, chapter 32. Chapman and Hall/CRC, 01 2004.  URL: https://www.cs.colostate.edu/~rmm/pc2.pdf, doi:10.1201/9781420035179.
  * [14] Wen-Lian Hsu and Ross M. McConnell.  PC trees and circular-ones arrangements.  Theoretical Computer Science, 296(1):99–116, mar 2003.  doi:10.1016/s0304-3975(02)00435-8.
  * [15] Sebastian Leipert.  PQ-trees, an implementation as template class in C++.  Technical report, University of Cologne, 1997.  URL: http://e-archive.informatik.uni-koeln.de/id/eprint/259.
  * [16] Wei-Kuan Shih and Wen-Lian Hsu.  A new planarity test.  Theoretical Computer Science, 223(1-2):179–191, jul 1999.  doi:10.1016/s0304-3975(98)00120-0.
  * [17] João Paulo Pereira Zanetti.  Complexidade de construção de árvores PQR.  Master’s thesis, Universidade Estadual de Campinas, Instituto de Computação, 2012.  URL: http://bdtd.ibict.br/vufind/Record/CAMP_0b551865d78ef032289f17f95e3ccee7.

Figure 9: Distribution of tree and restriction size for DIR-PLAN.

##  Appendix A Details About Evaluated Implementations

BiVoC, Gregable

In the implementations of _BiVoC_ and _Gregable_ , we improved the mapping
from the input to the tree’s leaves by replacing std::map with std::vector, as
suggested in the code’s comments. As a result, this mapping now takes constant
time. The Bubble method of BiVoC caused segmentation faults due to undefined
behavior, because a set iterator is dereferenced and incremented after its
corresponding element has been removed. We resolved this issue for our
evaluation. Still, the method qNextChild of BiVoC rarely caused program hangs
due to undefined behavior, when the past-the-end iterator of an empty set is
incremented. In the Gregable repository, the author notes that the code “is
known to be buggy on some rare inputs. A believed to be correct, but harder to
use version of this code can be found as a library within BiVoC”. However, in
contrast to BiVoC, Gregable’s implementation always produced the expected
results in our evaluation.

GraphSet

In the implementation of _GraphSet_ , we removed the entanglement with
Microsoft Foundation Classes by replacing its data structures with their
corresponding variants from the standard library. We were unable to get
GraphSet’s Bubble method to work for our tests. Instead, we used the approach
from their quadratic-time variant of Booth and Lueker’s planarity test, where
they traverse the entire tree before each reduction in order to find and
prepare the pertinent subtree. Still, GraphSet produced segmentation faults
due to null pointer dereferencing in Template Q3.

TryAlgo

In June 2020, the authors of the _TryAlgo_ implementation noted on their
website that they “have problems implementing this data structure, and cannot
provide at this point a correct implementation in tryalgo”. Furthermore, they
note that “the current implementation has a complexity in the order of $n*m$,
however an implementation in $O(n+m+s)$ is possible”. As we thus assumed their
implementation to be neither correct nor linear-time, we excluded it from our
evaluation.

SageMath

The main routine set_contiguous of the PQ-tree of _SageMath_ recursively
traverses the tree starting from its root as follows: it first calls
set_contiguous recursively on all children of the current node, then calls
flatten, calls set_contiguous recursively on all children again and then
proceeds to sort the children depending on whether they are full, partial, or
empty. The flatten function for removing degree-2 nodes is implemented to
recurse itself on all children in the subtree, making the runtime of
set_contiguous quadratic in the tree size. We modified the implementation to
only flatten the current level and dropped the second recursive call to
set_contiguous, improving the runtime to linear in the tree size without
generating incorrect results.

Zanetti

We found that _Zanetti_ ’s data structures became inconsistent after some
restrictions, which was also already independently reported on
GitHub.333https://github.com/jppzanetti/PQRTree/issues/2 This happened mostly
after restrictions having a terminal path length greater than 1. As the
restrictions generated when serializing a PC-tree only have very short
terminal paths and the inconsistency is usually only found when modifying the
same area of the tree again, only few of these cases surfaced in our tests on
SER-POS. Only when applying multiple bigger restrictions consecutively, these
issues surfaced more often, i.e. at some point during the planarity test for
close to all graphs with $m=2n$ and also some of the graphs with $m=3n-6$. We
also found a second, independent issue, where Zanetti’s implementation
generates C-nodes with their children in the wrong order. An examples where
this happens is shown in Figure 10.

As Zanetti’s Java implementation still has a very good runtime in practice, we
decided to port its Java code to C++ to be able to perform a direct comparison
with the other C++ implementations. As the implementation uses close to none
Java specific features, the conversion mostly involved replacing Java Object
variables with C pointers and Java utility classes with their C++ stdlib
equivalents. The only non-trivial change was that, because Zanetti stores the
Union-Find information directly in the nodes and not in an external array, we
had to implement reference counting for Zanetti’s tree nodes to ensure that
the lifetime of nodes which are no longer part of the tree, but still
referenced in the Union-Find data structure, is handled properly. We made sure
that both the Java and the C++ version not only produced equivalent output,
but actually keep the same PQR-tree state in memory. Where both
implementations differ is that Java immediately reports inconsistencies of the
data structure, e.g. by throwing a NullPointerException, while the SIGSEGFAULT
of C++ might not be immediately triggered. This generates a few more data
points with an invalid result, where the Java implementation already crashed.

Figure 10:  Left: The PQR-tree [0 1 2 (3 (4 5)) 6] not containing any R-nodes
with its root Q-node depicted as rectangle and the two P-nodes depicted as
small circles. Right: The result of Zanetti’s implementation applying the
restriction {3,4} to the former tree, the tree [[3 4 5] 0 1 2 6] which clearly
represents a different set of restrictions.

##  Appendix B Algorithmic Improvements

In this section, we describe further details in which our implementations
differ from the description given by Hsu and McConnell and explain the
corrections needed for a working implementation. Section B.1 describes the
labeling procedure used by HsuPC and UFPC. Note that the technical
complications involving the arcs and block-spanning pointers only concern the
missing C-node objects of HsuPC. UFPC uses direct references to the concerned
nodes instead of arcs and doesn’t maintain block-spanning pointers, which is
why those parts are not relevant for our second implementation, which is
otherwise based on HsuPC. The same holds for Section B.2, where we give a
corrected algorithm for enumerating the terminal path. Section B.3 then
describes the generic steps needed to detect impossible restrictions. Lastly,
Section B.4 explains the differing update step of UFPC, while the update step
of HsuPC follows Hsu and McConnells original description.

###  B.1 Efficiently Labeling and Finding Partial Nodes

In our description of the labeling step, we follow the general procedure of
Hsu and McConnell [13], using a bottom-up traversal of the tree, starting at
the full leaves. To implement this, we keep a queue of unprocessed non-full
arcs of full nodes, which is initialized with the parent arcs of all full
leaves. If the front of the queue knows its node object, this has to be a
P-node and we can simply append the incoming arc to the node’s list of full
children. Recall that each full node has exactly one non-full neighbor. Thus,
if this list reaches a size one smaller than the node’s degree, we enqueue the
parent pointer of the node, if it exists and the parent is not yet full. The
other case, when the now-full node is the root or when the parent has become
full before its child, is missing in the description by Hsu and McConnell.
Here, we need to search all children for the single non-full node, and queue
this arc instead. This case is rare and the search of all full children can
still be done in time linear in the number of full leaves, thus not affecting
the overall runtime.

If the arc does not point to a permanent (P-)node, we need to maintain (i.e.
create/append/merge) the block-spanning pointers around the respective C-node
$x$. The merging of full blocks is illustrated in Figure 11, see the book
chapter by Hsu and McConnell [13] for more details. If the new endpoints of
the C-node’s full block now share a common non-full neighbor, the C-node is
full and we queue this neighbor $z$. Note that similar to the case of P-nodes,
this node is most often but not necessarily (i.e. for the root) the parent
arc. Still, there is no explicit search required, as we already know the arc
to the only non-full neighbor.

(a)

(b)

Figure 11: (a) A newly created block $x$ of size one growing by one as the
neighboring arc $v$ becomes full and is appended. (b) Two blocks that share a
common neighbor $x$ being merged once $x$ becomes full. The block-spanning
pointers are shown as blue, dashed half-arcs.

In their definition of the data structure Hsu and McConnell note that “[n]o
two C nodes are adjacent, so each of these edges [incident to a C-node] has
one end that identifies a neighbor of the C node, and another end that
indicates that the end is incident to a C node, without identifying the C
node” [13, page 32-10]. Considering the PC-tree with 6 leaves representing the
restrictions $\\{\\{1,2\\},\\{2,3\\},\\{4,5\\},\\{5,6\\}\\}$, which consists
of two adjacent C-nodes and (up to reversal and circular shifting) only has
the two valid permutations $[1,2,3,4,5,6]$ and $[1,2,3,6,5,4]$, this statement
is obviously untrue. Hsu and McConnell use this property within their
planarity test and when they test whether the endpoints of a full block are
adjacent to the same arc: “[i]f $x$ passes this test, it is full, and the
full-neighbor counter of $z$ is incremented” [13, page 32-11]. According to
their argumentation, $z$ has to be a P-node as no two C nodes are adjacent,
which is incorrect. Still, the important information is not the type of the
nodes, but that the neighbor $x$ of non-full node $z$ became full, and our
queue-based approach also handles the case of a chain of multiple C-nodes
becoming full consecutively.

###  B.2 Efficiently Finding the Terminal Path

There are two possible structures for the terminal path, assuming the
restriction is possible. Let the _apex_ be the highest node on the terminal
path, i.e., the node that is an ancestor of all other nodes on the terminal
path. The two cases can now be differentiated based on the position of the
apex, which in turn depends on the position of the root node:

I-Shaped:

If the apex lies on one of the ends of the terminal path and is therefore a
terminal node at the same time, the terminal path extends from the other
endpoint of the path upwards to the apex, as shown in Figure 12(a). In this
case, every node on the terminal path has exactly one child on the terminal
path, except for the lower terminal node $t_{1}$. This also covers the special
case where the terminal path has length 0 and there is only a single terminal
node $t_{1}=t_{2}$.

A-Shaped:

If the apex does not lie on one of the ends of the terminal path, two
ascending paths join in the apex, as shown in Figure 12(b). In this case, the
apex $a$ has two children on the terminal path, the terminal nodes $t_{1}$ and
$t_{2}$ have none, and all other nodes on the terminal path have exactly one
child that is also on the terminal path.

(a)

(b)

Figure 12:  Two examples of a PC-tree with root $r$. (a) An I-shaped terminal
path where $t_{2}$ is both apex and terminal node. (b) An A-shaped terminal
path where two ascending paths join in the apex $a$.

Hsu and McConnell show that an edge is terminal if and only if it lies on a
path in the tree between two partial nodes. This allows them to conduct
parallel searches, starting at every partial node and extending ascending
paths through their ancestors at the same rate [13]. Whenever an already
processed node is encountered, expansion of the current path is stopped and
the path is instead merged into the path of the already processed node. This
bottom-up traversal can easily be done for P-nodes, but again as C-nodes have
no object registered with their incident arcs (i.e. except for a temporary one
stored at the two endpoints of their full block), finding their parent arc can
be difficult.

Hsu and McConnell distinguish two cases: Either they arrived at the C-node $x$
via an arc from a partial or empty node, or via an arc from a full node. In
the former case, they “look at the two neighbors of the child edge in the
cyclic order, and one of them must be the parent edge. This takes $O(1)$
time.” In the latter case, they “cycle clockwise and counterclockwise through
the edges to full neighbors. Of the first edges clockwise and counter-
clockwise that are not to full neighbors, one of these is the parent. In this
case, the cost of finding the parent is proportional to the number of full
neighbors $x$” [13, page 32-12]. Their procedure for the first case is
incorrect, as $x$ could also be the apex where both incident terminal arcs are
adjacent to each other, but not to the parent arc (note that if the apex $x$
is also the root, it doesn’t even have a parent arc; see Figure 13(b)). The
procedure for the second case is also incorrect, as $x$ could again be the
apex, where the parent arc (if it exists) is not necessarily adjacent to the
full block, as shown in Figure 13(d). Moreover, we can never arrive at $x$ via
an arc from a full node, as full nodes cannot be part of the terminal path.

To correctly implement this step, we again use a queue of unprocessed arcs
that may be part of the terminal path. We initialize the queue with the parent
arcs of all partial nodes found in the previous step, which is easy to do for
partial P-nodes. To find the parent arc of a C-node $x$, only knowing the two
endpoints of a full block from the labeling step, we fix the second case of
Hsu and McConnell’s case distinction as follows: If one of the two non-full
arcs adjacent to the full block is indeed the parent arc $p$ (see Figure
13(c)), we do simply continue the path in that direction by queuing $p$.
Otherwise, we store $x$ as apex candidate as we do not need to ascend any
further. This holds for the case when the parent arc $p$ is within the full
block, as a full node can not be part of the terminal path. If $p$ is located
somewhere else in the empty block, continuing the terminal path via that node
would make it impossible to later split the C-node $x$ into an (exclusively)
empty and an (exclusively) full half.

We now process the queue step by step, seeking the parent arc $p$ of the node
$x$ to which the removed arc $a$ points. When we encounter the root, we store
it as apex candidate and continue with the next entry of the queue. We also
never process a node twice, proceeding to the next entry if we detect this
case. The hard part now is again finding the parent pointer of a C-node $x$.
We first check whether the arcs next to the incoming arc $a$ are part of a
full block. If both are part of the same block, we can stop ascending as we
ran into a full node (the same holds for full P-nodes). If both are part of
two different full blocks, we abort and report an impossible restriction, as
there is no flip of $x$ that makes all full leaves consecutive. If only one is
part of a full block, we can use the procedure for initialization described in
the previous paragraph to find the parent arc.

Now consider the case where there is no full block adjacent to $a$, i.e. the
former case of Hsu and McConnells case distinction. If the parent arc $p$ is
actually adjacent to the incoming arc $a$, we follow that path and queue $p$
(see Figure 13(a)). Otherwise, the terminal path may continue as shown in
Figure 13(b), where one of the arcs adjacent to $a$ also belongs to the
terminal path and the current node $x$ is the apex. As we don’t know which of
the neighboring edges is terminal, we mark $a$ and store $x$ (identified by
its incident arc $a$) as the apex candidate. We can resolve this situation,
identify the second predecessor of $x$ and fix $x$ as actual apex if we later
process an arc that is adjacent to the accordingly marked arc $a$.

Observe that for each processed arc, we now either found a following parent
arc or marked the corresponding node as apex candidate. If we marked a node as
apex candidate and encounter it a second time when ascending from a different
node, we can be sure that the terminal path is A-shaped and the current node
actually is the apex. Otherwise, we can’t be sure that the apex candidate is
the actual apex if it is empty, as we might be extending an I-shaped path of
empty nodes above the actual apex. Thus, if the apex candidate is empty and
has only one predecessor, we find the actual apex by “backtracking” to the
next partial node below the apex candidate.

Furthermore, if there is only one element left in the queue and we haven’t
found an apex (candidate) yet, all parts of the terminal path have already
converged into a single ascending I-shaped path (instead of having met in an
A-shape and stopped at the apex) and we are again extending the terminal path
above the previously unidentified apex. We stop processing the queue and
backtrack to the next partial node below the last remaining element of the
queue. Otherwise, the queue processing also terminates if an impossible
restriction is detected (see Section B.3) or the queue runs empty, already
having identified the actual apex.

The backtracking needed to find the actual apex can be done in constant time
by storing, for each empty node on the terminal path, the highest partial node
in its subtree. Special care needs to be taken as an empty apex candidate may
collide with a later-found actual apex. In this case, we again extended an
I-shaped path of empty nodes above the previously unidentified apex and only
later found the second terminal path child of the apex, indicating that the
terminal path is actually A-shaped. As long as both the apex and the apex
candidate have the same node as highest partial node in their subtree, the
restriction is valid and the apex candidate can simply be discarded.

Observe that the number of arcs on the terminal path is proportional to the
length $p$ of the terminal path. Furthermore, we only check up to two
neighbors of each arc and any apex candidate requiring backtracking is at most
$p$ nodes above the actual apex. Thus, the overall runtime of our search for
the terminal path is in $O(p)$. Note that this slightly refines the analysis
of Hsu and McConnell [13], who sometimes scan the full children of a node and
thus have a runtime in $O(p+|R|)$.

(a) An _empty_ C-node that is part of a possibly _I-shaped_ terminal path.

(b) An _empty_ C-node that is _apex_ of an _A-shaped_ terminal path.

(c) A _full_ C-node that is part of a possibly _I-shaped_ terminal path.

(d) A _full_ C-node that is _apex_ of an _A-shaped_ terminal path.

Figure 13:  Different cases of the terminal path crossing a C-node. Empty,
partial, and full nodes are drawn in white, gray, and black, respectively. The
edges are oriented towards the root node. The green edges are part of the
terminal path, the blue dashed half-arcs depict the block-spanning pointers.
In cases (c) and (d), the node can be the final node of the terminal path,
i.e. a terminal node. Thus there might zero, one or two incident terminal
edges.

###  B.3 Efficiently Detecting Impossible Restrictions

Recall that a restriction is possible if and only if all terminal edges form a
path and all nodes on the terminal path can be flipped or rearranged such that
their empty and full children are consecutive while separated by the terminal
edges. The only way to violate the first property is when a node has more than
two incident terminal edges. P-nodes can detect directly when this case
occurs, while a C-node with more than two incident terminal edges either leads
to multiple apex candidates or detects the usage of one of its arc in multiple
paths. As P-nodes allow arbitrary arrangements of their children, only C-nodes
can violate the second property by either having multiple distinct full
blocks, by having a full block that is not adjacent to all incident terminal
edges, or by having no full block and two non-adjacent terminal edges. All
three cases lead to a disconnected terminal-path and thus multiple apex
(candidate) nodes, if the impossible restriction is not detected right away
because an arc would be part of two different paths. Thus, we know that the
restriction is impossible if and only if we either find a second, incompatible
apex (candidate) or a node has more than two incident terminal edges.

###  B.4 Deletion and Contraction

Deleting and inserting new edges is simple when using the arc-based tree
representation described by Hsu and McConnell. When using a doubly-linked tree
structure similar like the one used by UFPC, no explicit edge objects exists
and they are instead encoded by the child-parent relationship of the nodes.
This means that in Items 5 and 6 of the update procedure, the child-parent
relationship needs to be set immediately and correctly for every change and
cannot easily be updated later, as done by Hsu and McConnell. Thus, UFPC uses
a different approach for these two steps: First, the central node is created
and we make sure that it already has its final neighbors. This is trivial if
the apex is a C-node and thus can simply be reused as is. Otherwise, we create
a new C-node and add up to 4 neighbors: the apex’ first child on the terminal
path, a newly created P-node that was reassigned as parent of all full
children of the apex, the second child on the terminal path, and finally the
apex with all its empty children remaining. Note that not all four neighbors
might exist or be required, e.g. when the apex has no full or empty children.
Furthermore, the root of the tree is either among the full or the empty
children and thus the node that is still connected to the root needs to be
installed as parent of the new central node. Second, we iteratively contract a
child of the central node that is part of terminal path into the central node.
C-nodes can again be simply merged, while a P-node $x$ needs to be split into
a full and empty node. P-node $x$ is then replaced by the full node and the
empty node with the other terminal path neighbor of $x$ in between, if the
latter exists.