PQ Trees, PC Trees, and Planar Graphs:Planar Graphs

Planar Graphs

In this section, we describe an algorithm due to Shih and Hsu [34] that uses PC trees to recognize whether a graph H is planar. If it is, the algorithm returns a planar embedding, and if it is not, it points out a subgraph that is a subdivision of a K3,3 or a K5.

Linear time planarity test was first established by Hopcroft and Tarjan [13] based on a path addition approach, which finds a path in the graph and uses it to break the problem down recursively. A vertex addition approach, originally developed by Lempel, Even and Cederbaum [24], was later improved by Booth and Lueker [5] (hereafter, referred to as the B&L algorithm) to run in linear time using PQ trees. This approach adds one vertex at a time, updating the PQ tree to keep track of possible embeddings of the subgraph induced by vertices added so far. Both of these approaches are quite complex. Furthermore, both approaches use separate algorithms for recognition and embedding (Chiba et al [8]). Several other approaches have also been developed for simplifying the planarity test (see for example [7, 31, 35, 36]) and the embedding algorithm [6, 30].

Shih and Hsu [33] developed a linear time test, which has been referred to as the simplest linear time planarity test by Thomas in his lecture notes [37]. Independently, Boyer and Myrvold discovered a similar algorithm to the PC tree approach [6]. Later, in [34], they implemented the algorithm based on PC trees, which will be referred to as the S&H algorithm. When the given graph is not planar, the algorithm immediately produces explicit Kuratowski subgraphs. Furthermore, the recognition and embedding are done simultaneously in the algorithm.

Preliminaries

To represent a planar embedding, it suffices to find, for each vertex, the clockwise circular ordering induced by the planar embedding on its incident edges. Given these circular orderings, there are algorithms that can assign spatial coordinates to the nodes. Here, we deal only with the problem of finding these circular orderings, and refer to them collectively as the embedding of the graph.

As the algorithm progresses, more of the embedding becomes known. In particular, S&H comes to know the cyclic order of edges incident to a subset of the vertices. When the cyclic order of a vertex is known, it does not know whether this order should be clockwise or counterclockwise in the embedding, so it uses a C node to represent its cyclic order.

FIGURE 32.10: A cycle replacement consists of selecting a cycle in a graph, adding a new C node whose neighbors ordering gives the ordering of nodes on the cycle, and deleting the edges of the cycle.

As we illustrate in parts C and D of Figure 32.11, below, it is applied to a graph that arises partway into the induction step. It’s inverse operation is a C-node replacement.

Collectively, the C nodes represent the partial embedding known so far. Let us call such a graph with C nodes a constrained graph. The data structure for implementing the C node is the same as the one given in Definition 32.1; the algorithm continues to ensure that no two C nodes are adjacent.

If T is a depth-first spanning tree (DFS tree) of an undirected graph G, all edges of G are tree edges (edges of T ) or back edges (edges between a descendant and an ancestor in T [9]. A vertex is a back vertex if it has an incident back edge from one of its descendants.

Since there are n − 1 edges in T , the number of back edges is m − n + 1. We may therefore refer to the number of back edges without reference to any particular DFS tree.

A cut set is a set of vertices of a connected graph whose removal from the graph disconnects it. An articulation vertex in a graph is a vertex whose deletion disconnects the graph. A graph is biconnected if it has no articulation vertex [9]. A biconnected component of a graph is a maximal biconnected subgraph. The articulation vertices can be found in linear time [9], so it suffices to embed each biconnected component separately, and then connect them by their adjoining articulation vertices. Henceforth, therefore, we may assume that G is biconnected.

Given a planar embedding of a constrained graph G, and a cycle C in G that is a cut set, let us say that C’s subembedding is C and everything internal to it in the embedding.

A C-node replacement is the following operation (See Figure 32.10): If (y1, y2, ..., yk, y1) is the cyclic order of neighbors of x, install an edge yiy(i+1)modk for each i from 1 to k, then delete x. This replaces x with the cycle (y1, y2, ..., yk , y1). A cycle replacement is the inverse of this operation: select a cycle C, and insert a new C node x whose cyclic ordering of neighbors gives the vertices of C in order, and then delete the edges of C.

The Strategy

The algorithm of S&H can be described as a recursive algorithm, Embed. The graph passed to the initial call has no C nodes, but graphs passed to lower calls will have them. A DFS spanning tree is also passed to the call, and since the DFS tree may contain C nodes, it is a PC tree.

For now, assume that the initial graph is planar; later, we show how to modify the

FIGURE 32.11: The Embed operation. Embed finds a cycle C and its subembedding A in an unknown planar embedding of G. Embed removes elements of A that are internal to C, contracting resulting vertices of degree 2 on C, and performs a cycle replacement on C, inserting a new C node x. It then performs contractions to eliminate C-node neighbors of x. The result is the graph Gl. By induction on m − n + 1, a recursive call can be used to find an embedding of Gl. Performing a C-node replacement of x gives a planar embedding where C is a face; inverting the foregoing operations inserts the planar embedding of A inside of it.

algorithm so that it returns a Kuratowski subgraph when this is not the case. The input graph to each recursive call is also biconnected. Embed works by induction on the number

m − n + 1 of back edges (see Figure 32.11):

1. Choose a cycle C that is a cut set and return its subembedding A in some unknown planar embedding of G (Figure 32.11, part A).

2. Remove elements internal to A to obtain graph G2, which has a planar embedding where C is a face (Figure 32.11, part B).

3. Contract nodes on C that now have degree 2 to obtain a cycle Cl (Figure 32.11, part C).

4. Perform a cycle replacement on Cl to obtain a constrained graph G3 (Figure 32.11, part D).

5. Perform edge contractions between adjacent C nodes in G3 to obtain a a biconnected constrained graph Gl where no two C nodes are adjacent (Figure 32.11, part E).

6. By induction on the number m−n+1 of back edges, we may call Embed recursively on Gl to obtain a planar embedding of it.

7. On the planar embedding of Gl, perform the inverses of steps 6, 5, 4 and 3 to obtain a planar embedding of G.

The reason for contracting nodes on C of degree two in Step 3 is to ensure that, like G, Gl is biconnected. Failure to do so would result in pendant nodes, such as node c in Figure 32.10.

Because of the way C is selected, the base case will be a biconnected constrained graph G with a vertex n such that G − n is a PC tree. G − n is trivial to embed, and since this embedding has only one face, it is trivial to add n and its incident edges to this embedding to obtain an embedding of G.

Implementing the Recursive Step

Let us name the vertices according to their postorder numbering on a DFS tree T of G. If i is a vertex, we let Ti denote the subtree of T rooted at i. Let us say that a vertex j is earlier than vertex i if j < i.

The following are the inputs to Embed.

I1: A biconnected constrained graph G.

I2: The earliest back vertex i in T ;

I3: A DFS tree T of G where all C nodes in the tree are earlier than i. The DFS tree is implemented as in Definition 32.1, except that the circular lists of edges incident to a C node can include non-tree edges. The parent bits of Definition 32.1 are required only on tree edges, and are consistent with the rooting of the DFS tree.

I4: An ordered list of i and all later vertices, ordered in postorder on the DFS tree.

The Terminal Path

Let i be the earliest back vertex, let r be a child of i in the DFS tree whose subtree Tr in the DFS tree has a back edge to i. Since r is earlier than i, Tr is an induced subgraph of the constrained graph G that has no back edges, hence it is a tree.

A trivial case occurs when i is the root n of the DFS tree. Since G is biconnected, n is not an articulation vertex, so Tr is unique, and Tr = G − n. Tr is trivial to embed, and since this embedding has only one face, it is also trivial to add n and its incident edges to this embedding. This is the base case referred to in Section 32.3.2.

Otherwise, i < n. For ease of presentation, let us imagine, but not explicitly create, an unrooted tree T l as follows. For each edge (x, j) from a node x of Tr to a node j ≥ i, add an edge ( jx ) to Tr . Note that this applies to the tree edge (r, i), yielding (r, ir ). The result is a PC tree, but there may be multiple copies of each back vertex j, one for each edge from a node of Tr to j.

By analogy to Section 32.2.2, let us consider a leaf jx of T l to be full if j = i and empty otherwise. Since G is biconnected, every leaf of Tr has a neighbor greater than or equal to i; otherwise, its neighbor in Tr would be an articulation vertex. Therefore, every node of Tr is an internal node in T l. In addition, since i< n and i is not an articulation vertex, Tr has edges both to i and to proper ancestors of i, so T l has both empty and full leaves. Finally, since i has an incident tree edge and an incident back edge from Tr , T l has at least two full leaves.

As in Section 32.2.2, let us consider an internal node x to be full if there is a rooting of T l where x’s subtree only has full leaves, and empty if there exists a rooting where its subtree

FIGURE 32.12: The induction step of Embed. The cycle C selected by Embed consists of i, the terminal path, and the leftmost and rightmost paths to i from the terminal nodes after full and empty subtrees have been flipped to opposite sides of the terminal path (A). The full nodes and their back edges are trivial to embed inside C, since all of their back edges go to i. The nodes internal to C are to be removed. If they are removed, however, the nodes on the paths from i to the terminal nodes will have degree 2 so they can contracted out of the cycle. The net effect is to remove all full nodes from G, and leave a cycle consisting of i and the terminal path. This is accomplished by splitting the terminal path, as in the consecutive-ones problem, removing the full side of the split, and inserting an edge from i to each terminal node (B). A cycle replacement is performed on this cycle (C), and, as in the consecutive-ones problem, an order-preserving contraction is performed to remove C-node neighbors of of the new C node (D). This yields Gl; performing a recursive call on Gl and inverting the steps from A to D on the resulting embedding gives a planar embedding of G.

only has empty leaves. It is a terminal edge if neither of its endpoints is full or empty. If the terminal edges form a path, this is the terminal path. If there are terminal edges but they do not form a path, then T l has no terminal path. As before, if there are no terminal edges, the terminal path has length 0 and consists of a single node.

We give a proof of the following in Section 32.3.5:

LEMMA 32.3 If the constrained graph G has a planar embedding, it has a terminal path, and nodes on this path can be flipped so that all full subtrees lie on one side and all empty subtrees lie on the other, without violating the cyclic order of any C node.

This gives a planar embedding of T l in which all copies of i can be joined without crossing any back edges, as illustrated in Figure 32.12 (A). By the definition of Tr , there must be a back edge to i, and since G is biconnected, there must be a back edge from Tr to a proper ancestor of i; otherwise i would be an articulation vertex, since we are in an induction step where i j= n. The full subtrees, the terminal path, and i form an induced subgraph with a bounding cycle in this embedding. This bounding cycle is the cycle C referred to in the overview of the algorithm in Section 32.3.2.

As described in the overview, only the cycle, minus its nodes of degree two, is retained for the recursive call (Figure 32.12, part B), and it is replaced by a C node (Figure 32.12, part C). This results in adjacent C nodes whenever there is a C node on the terminal path, which is remedied with an O(1)-time contraction is performed on them, as depicted in Figure 32.9, with a result illustrated in Figure 32.12, part D.

A recursive call on the resulting graph provides an embedding of it. Inverting the operations depicted in parts D through B of Figure 32.12 yields a face into which the already- known embedding of the full subtrees can be inserted to yield a planar embedding of the original constrained graph.

Finding the Terminal Path

We use the full-partial labeling algorithm of Section 32.2.2 to label the full internal nodes of T l. This does not require creating T l explicitly, since Tr and its back edges represent Tr implicitly, and the full-partial labeling algorithm can be run on this representation by considering i to be full and its ancestors to be empty.

However, we must confront an annoying detail that we didn’t have in Section 32.2.2, which is that internal nodes can have degree 2. This allows the possibility that an internal node can be both empty and full. This can happen as follows. Let x be a full node, let y be an empty neighbor of degree 2, and let z be y’s other neighbor. Rooting T l at z gives y a subtree whose leaves are all full, and rooting it at x gives y a subtree whose leaves are all empty. Therefore, y is ambiguous.

If it is run without modification, the full-partial labeling algorithm of Section 32.2.2 will label ambiguous nodes as full. However, we can detect the first time it labels an ambiguous node y. In this case, x is a full neighbor that has just notified y that it is full. If x has degree 2, then it is also ambiguous, contradicting our choice of y. If it has degree 1, it is the only full leaf, contradicting the fact that T l has at least two full leaves. Therefore, x

has degree greater than two, and full leaves can be reached from y only by going through x.

This situation is easily detected: when it is time for x to notify y that it has become full, x is the only node that has been labeled full but not yet notified its non-full neighbor, and y has degree 2. In this case, we halt the full-partial labeling algorithm early, and select x to be the only node in a terminal path of length 0. Aside from this detail, the full-label algorithm is the same as in Section 32.2.2.

By the analysis of Lemma 32.1, the running time is proportional to the number of terminal edges plus the number of full nodes if the conditions of Lemma 32.3 are met. If they are not met, the graph can be rejected. However, in this case, we still want to know the terminal edges since we will use them to produce a Kuratowski subgraph. The algorithm for finding them is easily implemented to run in time proportional to the size of G in this case, as it requires finding only the subtree of edges that lie on paths between partial nodes. They can be labeled by rooting the tree at one of the partial nodes and working upward from the other partial nodes.

The Linear Time Bound

The analysis of the complexity of the full-partial algorithm of Section 32.2.2 made use of the fact that there are no nodes of degree two. We have not ensured that this is true of T l.

The main problem that this causes is that the number of full nodes is not asymptotically bounded by the number of full leaves, so we can no longer claim that the running time of the full-partial labeling algorithm is bounded by the number of full leaves.

Instead, S&H makes use of the observation that all full nodes are deleted from the recur- sive call. We may therefore use a potential function that charges the costs of the full-partial labeling algorithm to nodes and edges that are removed from the recursive call, at O(1) cost per node or edge.

The potential function is similar to the one for the consecutive-ones property, except that ui denotes the number of nodes and edges of the graph:

We show that the value of the potential function for the recursive call drops by an amount proportional to the set of operations performed outside of the recursive call, such as running the full-partial labeling algorithm.

The analysis of the cost of the O(p) operations is unaffected. Since the full nodes are deleted, the Ω(k) drop in the potential function pays for the remaining O(k) operations. The remaining operations of finding the terminal path are analyzed as in the consecutive-ones problem.

Finding and splitting the terminal path is performed just as it is in the consecutive-ones problem. By Lemmas 32.1 and 32.2, this takes time proportional to the number k of full nodes plus the length p of the terminal path, and covers the cost of removing the nodes internal to C illustrated in Figure 32.12 (B).

We must now analyze the cost of meeting the preconditions I1-I4 in each recursive call. I1 through I4 can easily be met in O(n + m) time for the initial call, where all nodes are P nodes, using standard techniques from [9].

Given I1 - I4 for G, we describe how to modify them so that they can be met in the recursive call on Gl.

LEMMA 32.4 A rooted spanning tree of an undirected graph is a DFS tree if and only if all non-tree edges are back edges.

The necessity of this condition is common knowledge [9]. For the sufficiency, observe that if T is a rooted spanning tree such that every non-tree edge is a back edge, then ordering the adjacency lists so that tree edges appear first and calling DFS at the root of T will force it to adhere to T as the DFS tree.

For Input I4, let T l be the DFS tree passed to the recursive call. Since all differences between T and T l occur in subtree Ti, the postorder of elements later than i in T is also the same as in T l. The input is met by searching forward in the preorder list for the next back vertex, and discarding the traversed elements from the front of the list.

For Input I3, let us make the new C node x inserted inside C be a child of i, hence a parent of its other neighbors in the DFS tree that is passed to the recursive calls. This requires us to label the parent-bit labels of edges incident to the new C node before contractions, as in Figure 32.12 (C). We have already bounded the cost of touching these edges, so this does not affect the asymptotic running time. Any remaining C nodes that are removed by O(1)-time contractions, as in Figure 32.12 (D) have the contracted edge as their parent edge, so the new node becomes the parent of their empty subtrees, without requiring any further relabeling of parent bits.

Since all back edges in T go from descendants to ancestors, it is easy to see that this is also true of T l. T l is a depth-first spanning tree of Gl, by Lemma 32.4, so the conditions of For Input I1, Step 3 of the description of Section 32.3.2 ensures that every node on the cycle has an incident edge to an empty node in T l. Therefore, the remaining graph is biconnected, since for every node in Tr , there are two paths to a proper ancestor of i: one of them by traveling upward on tree edges, and one of them by traveling downward through an empty tree and then to the ancestor on a back edge.

For Input I2, if i ceases to be a back vertex in Gl, then vertices are examined in ascending  order in the list I4, starting at i until the next back vertex, il, is encountered. Since these searches are monotonically increasing, the total costs of them over all recursive calls is linear.

Differences between the Original PQ-Tree and the New PC-Tree Approaches

Whenever a biconnected subgraph is created, the algorithm uses a subset of vertices in its bounding cycle as representatives to be used for future embedding. The embedding of each biconnected component is temporarily stored so that, at base case, when the graph is declared planar, a final embedding can be constructed by tracing back and pasting the internal embedding of each biconnected component inside its bounding cycle.

The way S&H adopted PC trees in their planarity test is entirely different from that of B&L’s application of PQ trees in Lempel, Even and Cederbaum’s planarity test [24]. B&L used PQ trees to test the consecutive ones property of all nodes adjacent to the incoming node in their vertex addition algorithm. The leaves of their PQ trees are exactly those nodes adjacent to the incoming node. Internal nodes of the PQ trees are not the original nodes of the graph. They are there only to keep track of feasible permutations, whereas in S&H’s approach, a P node is also a vertex of the original graph H, a C node denotes a biconnected subgraph, and nodes adjacent to the new node can be scattered anywhere, both as internal nodes and as leaves in the PC tree. Thus, S&H’s PC tree faithfully represents a partial planar embedding of the given graph and is a more natural representation. Another difference is that in order to apply PQ trees in Lempel, Even, and Cederbaum’s approach, there is a preprocessing step of computing the “s-t numbering” besides the depth-first search tree. This step could create a problem when one tries to apply PQ trees to find maximal planar subgraphs of an arbitrary graph [13].

Other aspects of handling the PC tree are adapted from B&L’s approach, such as the handling of of Q nodes (or C nodes) during execution of the full-partial labeling algorithm.

Returning a Kuratowski Subgraph when G is Non-Planar

In this section, let H denote the unconstrained graph that is passed into the initial call, let G denote the constrained graph that is passed into a lower recursive call, and let Gl denote the constrained graph that is passed into the next recursive call down from G.

The graph H passed in at the highest-level call has no C nodes. In any recursive call on a constrained graph G, all P nodes are vertices of H. Therefore, all neighbors of a C node are vertices of H.

LEMMA 32.5 A unique cycle C of H that has the following properties can be constructed from a C node x of G. Let (x1, x2, ..., xk ) be the cyclic order of x’s neighbors. Then (x1, x2, ..., xk ) appear in that order on C, and the remaining nodes of C were contracted in higher-level recursive calls by applications of Step 3 of Section 32.3.2.

Before proving this, let us examine what it implies about the relationship paths G and paths in H. A path in G through a C node x corresponds to two possible paths in H, one that proceeds in one direction about the cycle represented by x and one that proceeds in the other direction (Figure 32.13).

Proof We give the construction of the lemma by induction on the depth of a call. The initial call is the base case, where there are no C nodes and the claim is vacuously true. For the induction step, let x be the new C node created in the step, and let C be the separating cycle bounding the full nodes of G that is found in the step. Note that, as in

Figure 32.12, C may itself contain C nodes.

Let y be such a C node on C, and let a, b be its neighbors on C. By induction, the lemma applies to y, so y represents a cycle Cy of H.

The portion (a, y, b) of C represents two possible paths in H: one, P1, that travels one way around Cy avoiding empty neighbors of y in G (other than possibly a or b), and another, P2, that travels the other way, avoiding full neighbors of y in G (other than possibly a or b). When constructing the cycle Cx in H represented by x, splice in P2 in place of (a, y, b). This ensures that the neighbors of x in Gl will be on Cx in H.

After application of the contraction step 3, some additional nodes of the cycle bounding the full subtrees are contracted out before they have a chance to become neighbors of the new C node, but these are those that the lemma allows to be removed. Therefore, the induction hypothesis to apply x and Cx.

The constructive proof of the lemma shows how the cycle represented by a C node can be found in H, by undoing the contractions while returning up through the recursive calls to H.

We now show how to return a subdivision of a K3,3 or a K5 when the conditions of Lemma 32.3 are not met.

Suppose first that the terminal edges of T l do not form a path. Recall that a terminal edge is defined to be an edge whose removal from T l separates it into two subtrees that each have both full and empty nodes. Clearly, the terminal edges are connected, so they form a subtree of T l with at least three leaves, z1, z2, and z3. Let w be the meeting point of the paths of terminal edges that connect them, as illustrated in Figure 32.14. For zk ∈ {z1, z2, z3}, there is a path of non-terminal edges through full nodes, ending at a copy

FIGURE 32.14: When the terminal edges of T l do not form a path, they form a subtree of TC with at least three leaves, z1, z2, and z3, each of which is adjacent to a full subtree that has a copy of i and an empty subtree that has a copy of a proper ancestor of i. Let w be the node of the tree from which paths to z1, z2, and z3 branch.

of i, and a disjoint path of non-terminal edges through empty nodes, ending at a copy of a proper ancestor tk of i. Collectively, these paths correspond to paths in G that are disjoint, except at their endpoints. (The multiple copies of i are identified in G, and {t1, t2, t3} are not necessarily distinct.) There exists t ∈ {t1, t2, t3} of median height. The paths from z1, z2, and z3 to t1, t2, and t3 can be extended via edges of the DFS tree to paths to t that are disjoint except at t (Figure 32.15). These paths and the terminal edges joining them to w define a subdivision of a K3,3 of G with bipartition {{z1, z2, z3}, {w, i, t}}.

If w is a P node, this K3,3 of G expands to to a subdivision of K3,3 in H by Lemma 32.5.

If w is a C node, but at least one of z1, z2, and z3 fails to be a neighbor of w, then we can reduce this case to the previous one by taking into account that w represents a cycle in H by Lemma 32.5, and finding a P-node neighbor wl of w to serve in place of w, as illustrated in Figure 32.16. (Since no two C nodes are adjacent, wl is a P node.)

Suppose w is a C node and each of z1, z2, and z3 is a neighbor of w. Without loss of generality, suppose t2 is a minimal element of the not-necessarily distinct elements t1, t2, and t3. If t2 = t1 or t2 = t3, then S&H returns a K5; otherwise, the algorithm returns a K3,3, as illustrated in Figure 32.17.

Finally, let us consider the case when there are at most two terminal nodes, but it is not possible to flip the full subtrees to one side of the terminal path and the empty trees to the other, due to constraints imposed some C node x that lies on the terminal path.

For each neighbor y of x, let Ty be the neighboring subtree reachable from x through y. That is, it is the component of the PC tree that contains y when x is deleted, and, conceptually, its “leaves” are the leaves of this subtree if it is then rooted at y. If y lies on the terminal path, at least one of Ty ’s leaves is a copy of i and at least one is a copy of a proper ancestor of y. Otherwise, all of its leaves are copies of i or all are copies of proper ancestors, depending on whether Ty is full or empty.

The cyclic order of neighbors of x blocks flipping the full and empty subtrees to opposite sides of the terminal path iff x has four neighbors a, b, c, d whose cyclic order about x is (a, b, c, d), and and where Ta and Tc each contain a full leaf and Tb and Td each contain an empty leaf. (A neighbor on the terminal path can be selected for either of these two categories.)

Suppose that this is the case. In T l, there are disjoint paths from a and c through Ta and Tc to copies of i and from b and d through Tb and Td to copies of proper ancestors tb, td of i. These all correspond to paths of G that are disjoint except at their endpoints. If tb = td, let t = tb = td. Otherwise, let t be the lower of the two. The path to the other of the two can be extended by DFS tree edges to t that is still disjoint from the other paths, except

at t. These paths, the cycle represented by x, and the DFS tree edges between t and i give rise to a K3,3 of H by Lemma 32.5, as in Figure 32.18. In addition to giving an algorithm for returning a subdivision of a K3,3 or a K5 when the embedding algorithm fails, we have just proven Lemma 32.3, since no planar graph contains such a subdivision.