format: text

text:
# Common-Face Embeddings of Planar Graphs The preliminary form of this paper appeared in the proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 195-204.

## 1 Introduction

It is a fundamental problem in mathematics (e.g., see ) to embed a graph into a given surface while optimizing certain objectives required by applications. (Throughout this paper, a graph may have multiple edges and selfloops but a simple graph always has neither.) A graph is planar if it can be embedded on the plane so that any pair of edges can only intersect at their endpoints; a plane graph is a planar one together with such an embedding. A classical variant of the problem is to test whether a given graph is planar and in case it is, to find a planar embedding. This planarity problem can be solved in linear time sequentially  and efficiently in parallel .

In this paper, we initiate the study of the following new planarity problem. Let $`𝒢`$ be a planar graph. Let $``$ be a sequence $`𝒞_1,\mathrm{},𝒞_q`$, where each $`𝒞_i`$ is a family of vertex subsets of $`𝒢`$. A plane embedding $`\mathrm{\Phi }`$ of $`𝒢`$ satisfies $`𝒞_i`$ if the boundary of some face in $`\mathrm{\Phi }`$ contains at least one vertex from each set in $`𝒞_i`$. $`\mathrm{\Phi }`$ satisfies $``$ if it satisfies all $`𝒞_i`$. $`𝒢`$ satisfies $``$ if $`𝒢`$ has an embedding that satisfies $``$.

###### Problem 1 (the common-face embedding (CFE) problem)

* Input: A planar graph $`𝒢`$ and a sequence $``$ of families of vertex subsets of $`𝒢`$.
* Question: Does $`𝒢`$ satisfy $``$?

Let $`I`$ be the input size, i.e., the total number of vertices and edges in $`𝒢`$ and the families $`𝒞_i`$, counting multiplicity. We first show that the CFE problem is NP-complete in general. Then, for the special case where each vertex subset in each $`𝒞_i`$ induces a connected subgraph of $`𝒢`$, we give an $`O(I\mathrm{log}I)`$-time algorithm which can actually find a plane embedding satisfying $``$, if any exists. Note that the classical problem of simply finding a planar embedding is a further special case of this special case with $`q=0`$. Therefore, the processing of the additional constraints $`𝒞_1,\mathrm{},𝒞_q`$ only incurs a logarithmic factor of overhead.

The CFE problem arises naturally from topological inference . For instance, in the conference version of this paper , a less general and less efficient variant of our algorithm for the special case has been employed to design fast algorithms for reconstructing maps from scrambled partial data in geometric information systems . In this application , each vertex subset in $``$ describes a recognizable geographical feature and each face in a planar embedding represents a geographical region. Each family in $``$ is a set of features that are known to be near each other, i.e., surrounding the same region (on the boundary of the same face). Similarly, our algorithm for the special case can compute a constrained layout of VLSI modules , where each vertex subset consists of the ports of a module, and each subset family specifies a set of modules that are required to be close to each other .

To the best of our knowledge, the conference version of this paper is the first to investigate the CFE problem . A related problem has been studied in the context of speeding up the computation of Steiner trees and minimum-concave-cost network flows . Given a planar graph $`G=(V,E)`$ and a set of special vertices $`SV`$, the pair $`(G,S)`$ is called $`k`$-planar if all the vertices in $`S`$ are on the boundaries of at most $`k`$ faces of a planar embedding of $`G`$. Bienstock and Monma  showed that testing $`k`$-planarity is NP-complete if $`k`$ is part of the input but takes linear time for any fixed $`k`$.

The remainder of this paper is organized as follows. Section 2 proves the NP-completeness result and formally states the main theorem on the CFE algorithm (Theorem 2.2). Sections 3 through 6 prove the main theorem by detailing the algorithm for the key cases where $`𝒢`$ is (1) triconnected, (2) disconnected, (3) connected, or (4) biconnected, respectively. The triconnected case is the base case in that the other cases are eventually reduced to it. For this reason, this case is analyzed before the other cases. Section 7 concludes this paper with some directions for further research.

## 2 Basics and the main results

### 2.1 Basic definitions

Let $`G`$ be a graph. $`|G|`$ denotes the size of $`G`$, i.e., the total number of vertices and edges in $`G`$. $`𝒱(G)`$ denotes the vertex set of $`G`$. If $`G`$ is a plane graph, then $`(G)`$ denotes the set of faces of $`G`$.

A set $`U`$ is $`G`$-local if $`U𝒱(G)`$. A family $`𝒞`$ of sets is $`G`$-local if every set in $`𝒞`$ is $`G`$-local.

For a subset $`U`$ of $`𝒱(G)`$, the subgraph of $`G`$ induced by $`U`$ is the graph $`(U,E_U)`$ where $`E_U`$ consists of all edges $`e`$ of $`G`$ whose endpoints both belong to $`U`$; $`GU`$ denotes the subgraph of $`G`$ induced by $`𝒱(G)U`$.

A cut vertex of $`G`$ is one whose removal increases the number of connected components in $`G`$; a block of $`G`$ is a maximal subgraph of $`G`$ with no cut vertex. Let $`\mathrm{\Psi }(G)`$ denote the forest whose vertices are the cut vertices and the blocks of $`G`$ and whose edges are those $`\{v,B\}`$ such that $`v`$ is a cut vertex of $`G`$, $`B`$ is a block of $`G`$, and $`v𝒱(B)`$. Note that $`\mathrm{\Psi }(G)`$ is a tree if $`G`$ is connected.

$`G`$ is biconnected if it is connected and it has at least two vertices but no cut vertex. $`G`$ is triconnected if it is biconnected, it has at least three vertices, and the removal of any two vertices cannot disconnect it.

The size of a set $`S`$, denoted by $`|S|`$, is the number of elements in $`S`$. The size of a family $`𝒞`$ of sets, denoted by $`|𝒞|`$, is $`_S|S|`$ where $`S`$ ranges over all sets in $`𝒞`$. The size of a sequence $``$ of families of sets, denoted by $`||`$, is $`_𝒞|𝒞|`$ where $`𝒞`$ ranges over all families in $``$.

### 2.2 An NP-completeness result

###### Theorem 2.1

The CFE problem is NP-complete.

Proof.  We reduce the SATISFIABILITY problem  to the CFE problem. Let $`\varphi `$ be a CNF formula over variables $`x_1,\mathrm{},x_n`$ with $`n2`$. Let $`C_1,\mathrm{},C_m`$ be the clauses of $`\varphi `$, each regarded as the set of literals in it. We construct a simple biconnected planar graph $`𝒢=(V_1V_2,E)`$ as follows. $`V_1=\{x_1,\mathrm{},x_n\}\{\overline{x}_1,\mathrm{},\overline{x}_n\}\{c_1,\mathrm{},c_m\}`$. $`V_2=\{u_0,\mathrm{},u_n\}`$. For each $`x_i`$, $`𝒢`$ contains edges $`\{u_{i1},x_i\}`$, $`\{x_i,u_i\}`$, $`\{u_{i1},\overline{x}_i\}`$, $`\{\overline{x}_i,u_i\}`$. The only other edges of $`𝒢`$ are $`\{u_0,c_1\}`$, $`\{c_1,c_2\}`$, $`\{c_2,c_3\}`$, …, $`\{c_{m1},c_m\}`$, $`\{c_m,u_n\}`$, $`\{u_n,u_0\}`$. Let $``$ be the sequence $`\{\{c_1\},C_1\},\mathrm{},\{\{c_m\},C_m\}`$. Observe that in every plane embedding $`\mathrm{\Phi }`$ of $`𝒢`$, (1) the cycle $`c_1,\mathrm{},c_m,u_n,u_0`$ forms the boundary of some face $`F`$ and (2) for $`i=1,\mathrm{},n`$, exactly one of $`x_i`$ and $`\overline{x}_i`$ is on the boundary of the face other than $`F`$ whose boundary contains the path $`c_1,\mathrm{},c_m`$. Also, for every set $`S\{x_1,\mathrm{},x_n\}\{\overline{x}_1,\mathrm{},\overline{x}_n\}`$ with $`|S\{x_i,\overline{x}_i\}|=1`$ for all $`i=1,\mathrm{},n`$, $`𝒢`$ has a plane embedding where the boundary of some face contains the path $`c_1,\mathrm{},c_m`$ and the vertices in $`S`$. Therefore, $`\varphi `$ is satisfiable if and only if $`𝒢`$ satisfies $``$.

### 2.3 The main theorem

Although the input to the CFE problem is a planar graph $`𝒢`$, it is easy to see that $`𝒢`$ satisfies a given sequence $``$ if and only if its underlying simple graph (i.e., the simple graph obtained from $`𝒢`$ by deleting multiple edges and selfloops) satisfies the same $``$. Thus throughout the rest of this paper, unless explicitly stated otherwise, $`𝒢`$ and $``$ always denote the input simple graph and the input sequence to our algorithm for the CFE problem, respectively. Also, $`I`$ always denotes $`|𝒢|+||`$, i.e., the size of the input to our algorithm.

The next theorem is the main theorem of this paper. In light of this theorem, the remainder of the paper assumes that every vertex subset of $`𝒢`$ in $``$ induces a connected subgraph of $`𝒢`$.

###### Theorem 2.2

If every vertex subset in $``$ induces a connected subgraph of $`𝒢`$, then the CFE problem can be solved in $`O(I\mathrm{log}I)`$ time.

Proof.  We consider three special cases:

* Case M1: $`𝒢`$ is connected.
* Case M2: $`𝒢`$ is biconnected.
* Case M3: $`𝒢`$ is triconnected.

In §3, Theorem 3.8 solves Case M3 of the CFE problem faster than the desired time bound. In §4, Theorem 4.3 reduces this theorem to Case M1. In §5, Theorem 5.3 reduces Case M1 to Case M2. In §6, Theorem 6.1 uses Theorem 3.8 to solve Case M2 of the CFE problem within the desired running time. This theorem follows from Theorems 4.3, 5.3, and 6.1.

As mentioned in Section 1, Case M3 is the base case, meaning that the other cases are eventually reduced to it. So, the next section describes an algorithm for this case.

## 3 Solving Case M3 where $`𝒢`$ is triconnected.

This section assumes that $`𝒢`$ is triconnected. Then, $`𝒢`$ has a unique combinatorial embedding up to the choice of the exterior face . Thus, the CFE problem reduces in linear time to that of finding all the faces in the embedding whose boundaries intersect every set in some $`𝒞_i`$. The naive algorithm takes $`\mathrm{\Theta }(|𝒢|||)`$ time. We solve the latter problem more efficiently by recursively solving Problem 2 defined below.

Throughout this section, for technical convenience, the vertices of a plane graph are indexed by distinct positive integers. The faces are indexed by positive integers or $`1`$. The faces indexed by positive integers have distinct indices and are called the positive faces. Those indexed by $`1`$ are the negative faces.

Let $``$ be a plane graph. A vf-set of $``$ is a set of vertices and positive faces in $``$. A vf-family of $``$ is a family of vf-sets of $``$. A vf-sequence of $``$ is a sequence of vf-families of $``$. For a vf-family $`𝒟=\{S_1,\mathrm{},S_d\}`$ of $``$, we define $`\mathrm{\Lambda }_\mathrm{f}(,𝒟)`$ and $`\mathrm{ACF}(,𝒟)`$ as follows:

1. $`\mathrm{\Lambda }_\mathrm{v}(,𝒟)=_{i=1}^dS_i𝒱()`$.
2. $`\mathrm{\Lambda }_\mathrm{f}(,𝒟)`$ is the set of positive faces $`F`$ of $``$ such that for each $`S_i𝒟`$, $`F`$ is a face in $`S_i`$ or its boundary intersects $`S_i\mathrm{\Lambda }_\mathrm{v}(,𝒟)`$.
3. $`\mathrm{ACF}(,𝒟)=\mathrm{\Lambda }_\mathrm{v}(,𝒟)\mathrm{\Lambda }_\mathrm{f}(,𝒟)`$.

###### Problem 2 (the all-common-face (ACF) problem)

* Input: A plane graph $``$ and a vf-sequence $`𝒩`$ of $``$.
* Output: $`\mathrm{ACF}(,𝒟_1),\mathrm{},\mathrm{ACF}(,𝒟_q)`$ where $`𝒟_1,\mathrm{},𝒟_q`$ are the vf-families in $`𝒩`$.

Throughout the rest of this section, $``$ and $`𝒩`$ always denote the input graph and the input sequence to our algorithm for the ACF problem, respectively.

To solve the ACF problem recursively, $``$ need not be simple or triconnected. Furthermore, those faces that are indexed by $`1`$ are ruled out as final output during recursions. To solve the problem efficiently, each vertex in $`\mathrm{\Lambda }_\mathrm{v}(,𝒟_i)`$ is meant as a succinct representation of all the faces whose boundaries contain that vertex. Similarly, the positive faces in the input $`𝒟_i`$ and the output are represented by their indices.

The next observation relates the CFE problem and the ACF problem.

###### Observation 3.1

Let the faces of $`𝒢`$ be indexed by positive integers. Then, the output to the CFE problem is “yes” if and only if for all $`𝒞_i`$, $`\mathrm{ACF}(𝒢,𝒞_i)\mathrm{}`$.

Section 3.1 proves a counting lemma useful for analyzing the time complexity of our algorithms for the ACF problem. Section 3.2 provides a technique for simplifying $``$ during recursions. Section 3.3 uses this technique to recursively solve the ACF problem without increasing the total size of the subproblems.

### 3.1 A counting lemma

###### Lemma 3.2

1. Let $`v_1`$ and $`v_2`$ be distinct vertices in $`𝒢`$. Let $`F_1`$ and $`F_2`$ be distinct faces in $`𝒢`$. Then, both $`v_1`$ and $`v_2`$ are on the boundaries of both $`F_1`$ and $`F_2`$ if and only if $`v_1`$ and $`v_2`$ form a boundary edge of both $`F_1`$ and $`F_2`$.
2. Given a set $`U`$ of vertices in $`𝒢`$, there are $`O(|U|)`$ faces in $`𝒢`$ whose boundaries each contain at least two vertices in $`U`$.
3. Given a set $`𝒫`$ of faces in $`𝒢`$, there are $`O(|𝒫|)`$ vertices in $`𝒢`$ which are each on the boundaries of at least two faces in $`𝒫`$.

Proof.  We prove the statements separately as follows.

Statement 1. This statement immediately follows from the condition that $`𝒢`$ is triconnected with no multiple edges.

Statement 2. Since $`𝒢`$ has no multiple edges, $`𝒢`$ contains $`O(|U|)`$ edges between distinct vertices in $`U`$. Then, this statement follows from Statement 1 and the fact that an edge in a simple plane graph can be a boundary edge of at most two faces.

Statement 3. If $`𝒢`$ has at most three vertices, the statement holds trivially. Otherwise, the statement follows from Statement 2 and the fact that the dual of $`𝒢`$ is also a simple triconnected plane graph .

###### Corollary 3.3

If $``$ is simple and triconnected, then the output of the ACF problem has size $`O(|𝒩|)`$.

Proof.  This corollary follows from Lemma 3.2(2).

### 3.2 Simplifying $``$ over a vf-set

To solve the ACF problem efficiently, we simplify the input graph $``$ by removing unnecessary edges and vertices as follows.

For a vf-set $`S`$ of $``$, the plane graph $`\mathrm{}S`$ of $``$ constructed as follows is said to simplify $``$ over $`S`$. An example is illustrated in Figures 1, 2, and 3.

Let $`𝒫_S`$ be the set of the positive faces in $``$ whose boundaries each contain at least two distinct vertices in $`S𝒱()`$. Let $`_S`$ be the plane subgraph of $``$ (1) whose vertices are those in $`S𝒱()`$ and the boundary vertices of the faces in $`(S())𝒫_S`$ and (2) whose edges are the boundary edges of the faces in $`(S())𝒫_S`$. Note that $`_S`$ inherits a plane embedding from $``$.

Let $`U_3`$ be the set of vertices which are of degree at least three in $`_S`$; note that each vertex in $`U_3`$ appears on the boundaries of at least two faces in $`(S())𝒫_S`$. A compressible path $`P`$ in $`_S`$ is a maximal path, which may be a cycle, such that (1) every internal vertex of $`P`$ appears only once in it, and (2) no internal vertex of $`P`$ is in $`SU_3`$. Note that by the choice of $`U_3`$, every internal vertex of a compressible path is of degree 2 in $`_S`$. We use this property to further simplify $`_S`$. Let $`\mathrm{}S`$ be the plane graph obtained from $`_S`$ by replacing each compressible path with an edge between its endpoints. This edge is embedded by the same curve in the plane as the path is. For technical consistency, if a compressible path forms a cycle and its endpoint is not in $`SU_3`$, then we replace it with a self-loop for the vertex of the cycle with the smallest index.

Each vertex in $`\mathrm{}S`$ is given the same index as in $``$. Note that the closure of the interior of each face of $`\mathrm{}S`$ is the union of those of several faces or just one in $``$. Let $`F`$ be a face in $`\mathrm{}S`$ and $`F^{}`$ be one in $``$. Let $`\sigma `$ (respectively, $`\sigma ^{}`$) denote the closure of the interior of $`F`$ (respectively, $`F^{}`$). If $`\sigma =\sigma ^{}`$, then $`F`$ and $`F^{}`$ are regarded as the same face, and $`F`$ is assigned the same index in $`\mathrm{}S`$ as $`F^{}`$ is in $``$. For technical conciseness, these two faces are identified with each other. If $`\sigma `$ is the union of the closures of the interiors of two or more faces in $``$, $`F`$ is not the same as any face in $``$ and is indexed by $`1`$. This completes the definition of $`\mathrm{}S`$.

###### Lemma 3.4

1. Given $``$ and $`S`$, we can compute $`\mathrm{}S`$ in $`O(||+|S|)`$ time.
2. Let $`S^{}`$ be a vf-set of $`\mathrm{}S`$. If $`S^{}S`$, then $`\mathrm{}S^{}=(\mathrm{}S)\mathrm{}S^{}`$.
3. If $``$ simplifies $`𝒢`$ over a vf-set $`S^{}`$ with $`SS^{}`$, then $`|\mathrm{}S|=O(|S|)`$.

Proof.  Statements 1 and 2 are straightforward. To prove Statement 3, it suffices to prove $`|𝒢\mathrm{}S|=O(|S|)`$ since by Statement 2, $`\mathrm{}S=𝒢\mathrm{}S`$.

To bound the number of vertices in $`𝒢\mathrm{}S`$, let $`𝒫_S`$ and $`U_3`$ be as specified in the definition of $`𝒢\mathrm{}S`$. Let $`U_1`$ be the set of vertices $`v`$ in $`𝒢\mathrm{}S`$ such that $`v`$ appears on the boundary of exactly one face in $`(S(𝒢))𝒫_S`$. Then, $`(S𝒱(𝒢))U_3U_1`$ consists of all the vertices in $`𝒢\mathrm{}S`$. Note that $`|U_1||(S(𝒢))𝒫_S|`$. Also, by Lemma 3.2(3), $`|U_3|=O(|(S(𝒢))𝒫_S|)`$. Consequently, since by Lemma 3.2(2) $`|𝒫_S|=O(|(S𝒱(𝒢))|)`$, $`|(S𝒱(𝒢))U_3U_1|=O(|S|)`$ as desired.

To bound the number of edges in $`𝒢\mathrm{}S`$, we first examine the multiple edges. Let $`u`$ and $`v`$ be adjacent vertices in $`𝒢\mathrm{}S`$. Let $`X_{u,v}`$ be the set of faces in $`(S(𝒢))𝒫_S`$ whose boundaries contain both $`u`$ and $`v`$. Then, $`|X_{u,v}|1`$. By Lemma 3.2(1), $`|X_{u,v}|2`$. If $`X_{u,v}=\{F\}`$, then the two boundary paths of $`F`$ between $`u`$ and $`v`$ may degenerate into at most two multiple edges between $`u`$ and $`v`$ in $`𝒢\mathrm{}S`$. If $`X_{u,v}=\{F_1,F_2\}`$, then by the triconnectivity of $`𝒢`$, $`F_1`$ and $`F_2`$ share exactly one common boundary edge $`e`$, which is also an edge in $`𝒢\mathrm{}S`$. Let $`C_i`$ be the boundary of $`F_i`$ without $`e`$. $`C_1`$ and $`C_2`$ may degenerate into at most two multiple edges between $`u`$ and $`v`$ in $`𝒢\mathrm{}S`$. In summary, there are at most three multiple edges between two vertices in $`𝒢\mathrm{}S`$. Similarly, only the boundary of a face in $`S(𝒢)`$ can degenerate into a self-loop in $`𝒢\mathrm{}S`$; so, $`𝒢\mathrm{}S`$ has only $`O(|S|)`$ self-loops. By Euler’s formula, $`𝒢\mathrm{}S`$ has $`O(|S|)`$ edges as desired.

### 3.3 Algorithms for the ACF problem

Throughout this subsection, let $`𝒟_1,\mathrm{},𝒟_q`$ be the vf-families in $`𝒩`$. To solve the ACF problem recursively, we use simplification to reduce the number of $`𝒟_i`$ and the number of sets in each $`𝒟_i`$.

For brevity, we define several notations. For a vf-family $`𝒟`$ of $``$, let $`\mathrm{}𝒟=\mathrm{}(_{S𝒟}S)`$. For a vf-sequence $`𝒩^{}`$: $`𝒟_1^{},\mathrm{},𝒟_p^{}`$ of $``$, let $`\mathrm{}𝒩^{}=\mathrm{}(𝒟_1^{}\mathrm{}𝒟_p^{})`$. For a vf-set $`S^{}`$ of $``$ and a vf-family $`𝒟`$ of $``$, we say $`𝒟S^{}`$ if $`SS^{}`$ for all $`S𝒟`$. For a vf-set $`S^{}`$ of $``$, we say $`𝒩S^{}`$ if $`𝒟_iS^{}`$ for all $`𝒟_i`$, $`1iq`$.

Lemmas 3.5 and 3.6 below reduce to $`1`$ the number of $`𝒟_i`$ in $`𝒩`$ in the ACF problem.

###### Lemma 3.5

Assume $`q2`$. Let $`𝒩_{\mathrm{}}=𝒟_1,\mathrm{},𝒟_{q/2}`$ and $`𝒩_r=𝒟_{q/2+1},\mathrm{},𝒟_q`$. Let $`_{\mathrm{}}=\mathrm{}𝒩_{\mathrm{}}`$ and $`_r=\mathrm{}𝒩_r`$.

1. Given $``$ and $`𝒩`$, we can compute $`_{\mathrm{}}`$ and $`_r`$ in $`O(||+|𝒩|)`$ total time.
2. For $`1iq/2`$, $`\mathrm{}𝒟_i=_{\mathrm{}}\mathrm{}𝒟_i`$. Similarly, for $`q/2+1iq`$, $`\mathrm{}𝒟_i=_r\mathrm{}𝒟_i`$.
3. If $``$ simplifies $`𝒢`$ over a vf-set $`S^{}`$ with $`𝒩S^{}`$, then $`|_{\mathrm{}}|=O(|𝒩_{\mathrm{}}|)`$ and $`|_r|=O(|𝒩_r|)`$.

Proof.  The three statements follow from those of Lemma 3.4, respectively.

###### Lemma 3.6

Assume $`q1`$. Let $`_i=\mathrm{}𝒟_i`$.

1. $`\mathrm{ACF}(,𝒟_i)=\mathrm{ACF}(_i,𝒟_i)`$.
2. If $``$ simplifies $`𝒢`$ over a vf-set $`S^{}`$ with $`𝒩S^{}`$, then $`|_i|=O(|𝒟_i|)`$.
3. If $``$ simplifies $`𝒢`$ over a vf-set $`S^{}`$ with $`𝒩S^{}`$, then given $``$ and $`𝒩`$, we can compute all $`_i`$ in $`O(||+|𝒩|\mathrm{log}(q+1))`$ total time.

Proof.  We prove the statements separately as follows.

Statement 1. The proof is straightforward. Note that a positive face in $`_i`$ is also a positive face in $``$ and that a negative face in $`_i`$ combines one or more faces not in $`\mathrm{ACF}(,𝒟_i)`$.

Statement 2. The proof follows from Lemma 3.4(3).

Statement 3. The graphs $`_i`$ can be computed by applying Lemma 3.5 recursively with $`O(\mathrm{log}(q+1))`$ iterations. By Lemma 3.5(1), the first iteration takes $`O(||+|𝒩|)`$ time. By Lemmas 3.5(3) and 3.5(1), each subsequent iteration takes $`O(|𝒩|)`$ time. By Lemma 3.4(2), the constant coefficient in the $`O(|𝒩|)`$ term does not accumulate over recursions.

Lemma 3.7 below solves the ACF problem with only one $`𝒟_i`$ in $`𝒩`$.

###### Lemma 3.7

Let $`𝒟=\{S_1,\mathrm{},S_d\}`$ be a vf-family of $``$ where $`d1`$. Let $`𝒟_{\mathrm{}}^{}=\{S_1,\mathrm{},S_{d/2}\}`$ and $`𝒟_r^{}=\{S_{d/2+1},\mathrm{},S_d\}`$. Let $`_{\mathrm{}}=\mathrm{}𝒟_{\mathrm{}}^{}`$; $`_r=\mathrm{}𝒟_r^{}`$; and $`𝒟^{\prime \prime }=\{\mathrm{ACF}(_{\mathrm{}},𝒟_{\mathrm{}}^{}),\mathrm{ACF}(_r,𝒟_r^{})\}`$.

1. $`\mathrm{ACF}(,𝒟)=\mathrm{ACF}(,𝒟^{\prime \prime })`$.
2. If $``$ simplifies $`𝒢`$ over a vf-set $`S^{}`$ with $`𝒟S^{}`$, then given $``$ and $`𝒟`$, $`\mathrm{ACF}(,𝒟)`$ can be computed in $`O(||+|𝒟|\mathrm{log}(d+1))`$ time.

Proof.  The statements are proved separately as follows.

Statement 1. Note that $`\mathrm{ACF}(,𝒟)=\mathrm{ACF}(,\{\mathrm{ACF}(,𝒟_{\mathrm{}}^{}),\mathrm{ACF}(,𝒟_r^{})\})`$ by a straightforward case analysis. Then, as Lemma 3.6(1), $`\mathrm{ACF}(,𝒟_{\mathrm{}}^{})=\mathrm{ACF}(_{\mathrm{}},𝒟_{\mathrm{}}^{})`$ and $`\mathrm{ACF}(,𝒟_r^{})=\mathrm{ACF}(_r,𝒟_r^{})`$.

Statement 2. We compute $`\mathrm{ACF}(,𝒟)`$ recursively via Statement 1. If $`d=1`$, then $`\mathrm{ACF}(,𝒟)=S_1`$. If $`d=2`$, then $`\mathrm{ACF}(,𝒟)`$ can be computed in $`O(||)`$ time in a straightforward manner. For $`d>2`$, there are three stages:

1. Compute $`_{\mathrm{}}`$ and $`_r`$ in $`O(||+|D|)`$ time in a straightforward manner.
2. Recursively compute $`\mathrm{ACF}(_{\mathrm{}},𝒟_{\mathrm{}}^{})`$ and $`\mathrm{ACF}(_r,𝒟_r^{})`$.
3. Compute $`\mathrm{ACF}(,𝒟^{\prime \prime })`$ in $`O(||)`$ time in a straightforward manner, which is $`\mathrm{ACF}(,𝒟)`$ by Statement 1.

This recursive computation has $`\mathrm{log}d+O(1)`$ iterations. The recursion at the top level takes $`O(||+|𝒟|)`$ time. Every subsequent level takes $`O(|𝒟|)`$ time since by Lemma 3.4(3) $`O(|_{\mathrm{}}|)=O(|𝒟_{\mathrm{}}^{}|)`$ and $`O(|_r|)=O(|𝒟_r^{}|)`$. Note that by Lemma 3.4(2), the constant coefficient in the $`O(|𝒟|)`$ term does not accumulate over recursions.

The next theorem is the main result of this section.

###### Theorem 3.8

1. Let $`d`$ be the maximum number of vf-sets in any $`𝒟_i`$ in $`𝒩`$. If $``$ simplifies $`𝒢`$ over a vf-set $`S^{}`$ with $`𝒩S^{}`$, then the ACF problem can be solved in $`O(||+|𝒩|\mathrm{log}(d+q))`$ time.
2. Let $`d`$ be the maximum number of vertex sets in any $`𝒞_i`$ in $``$. Case M3 of the CFE problem can be solved in $`O(|𝒢|+||\mathrm{log}(d+q))`$ time.

Proof.  Statement 1 follows from Lemmas 3.6 and 3.7. Statement 2 follows from Observation 3.1, Statement 1, and the fact that $`𝒢`$ has a unique combinatorial embedding computable in linear time .

In §6.4, the algorithm for Case M2 of the CFE problem calls Theorem 3.8(2) to solve subproblems in which some $`S𝒞_i`$ may consist of a single edge $`\{u,v\}`$. For such subproblems, we replace $`S`$ by $`\{u\}`$ and $`\{v\}`$ and then apply Theorem 3.8(2).

## 4 Reducing Theorem 2.2 to Case M1 where $`𝒢`$ is connected.

Let $`𝒢_1,\mathrm{},𝒢_k`$ be the connected components of $`𝒢`$. Let $`𝒞_1,\mathrm{},𝒞_q`$ be the families in $``$. A family $`𝒞_h`$ in $``$ is global if for every $`i\{1,\mathrm{},k\}`$, $`𝒞_h`$ is not $`𝒢_i`$-local. Let $`H`$ be an edge-labeled graph defined as follows. The vertices of $`H`$ are $`1,\mathrm{},k`$. For each global $`𝒞_h`$, $`H`$ contains a cycle $`C`$ possibly of length 2 where (1) the vertices of $`C`$ are those $`i\{1,\mathrm{},k\}`$ such that some set in $`𝒞_h`$ is $`𝒢_i`$-local and (2) the edges of $`C`$ are all labeled $`h`$. See Figures 4(1) through 4(3) for an example of $`𝒢`$, $``$ and $`H`$.

###### Observation 4.1

Let $`H_1,\mathrm{},H_{\mathrm{}}`$ be the connected components of $`H`$. For each $`H_j`$, let $`𝒢_j^{}`$ be the subgraph of $`𝒢`$ formed by all $`𝒢_i`$ with $`i𝒱(H_j)`$. Let $`_j^{}`$ be the sequence of all $`𝒢_j^{}`$-local families in $``$. Then, $`𝒢`$ satisfies $``$ if and only if every $`𝒢_j^{}`$ satisfies $`_j^{}`$.

By Observation 4.1, we may assume that $`H`$ is connected. Let $`B_1,\mathrm{},B_p`$ be the blocks of $`H`$. Then, for each global $`𝒞_h`$, exactly one $`B_j`$ contains all the edges labeled $`h`$. For every $`B_j`$, let $`𝒰_j=_h𝒞_h`$ where $`h`$ rangers over all labels on the edges of $`B_j`$. For each $`𝒢_i`$, let $`_i`$ be the sequence consisting of the $`𝒢_i`$-local families in $``$ as well as the families $`𝒰_{j,i}=\{U𝒰_j|U`$ is $`𝒢_i`$-local$`\}`$ for all $`B_j`$ with $`i𝒱(B_j)`$. See Figure 4(4) for an example of $`_1,\mathrm{},_6`$ constructed from $`𝒢`$, $``$ and $`H`$ in Figures 4(1) through 4(3).

###### Lemma 4.2

$`𝒢`$ satisfies $``$ if and only if every $`𝒢_i`$ satisfies $`_i`$.

Proof.  The two directions are proved as follows.

$`()`$ Let $`\mathrm{\Phi }`$ be an embedding of $`𝒢`$ satisfying $``$. Let $`\mathrm{\Phi }_i`$ be the restriction of $`\mathrm{\Phi }`$ to $`𝒢_i`$. For each $`𝒢_i`$, our goal is to prove that $`\mathrm{\Phi }_i`$ satisfies $`_i`$. First, $`\mathrm{\Phi }_i`$ satisfies each $`𝒢_i`$-local family in $``$. Let $`B_j`$ be a block of $`H`$ with $`iB_j`$. We next prove that $`\mathrm{\Phi }_i`$ satisfies $`𝒰_{j,i}`$. Let $`i,i_1,\mathrm{},i_{\mathrm{}}`$ be the vertices of $`B_j`$. We claim that $`𝒢`$ has no cycle $`C`$ such that at least one but not all of $`𝒢_i`$, $`𝒢_{i_1},\mathrm{},𝒢_i_{\mathrm{}}`$ are inside $`C`$ in $`\mathrm{\Phi }`$. To prove by contradiction, assume that such $`C`$ exists. Then, some $`𝒢_x`$ with $`1xk`$ contains $`C`$. However, by the construction of $`H`$, no connected component of $`H\{x\}`$ contains all of $`i`$, $`i_1,\mathrm{},i_{\mathrm{}}`$, contradicting the fact that $`B_j`$ is a block of $`H`$. Thus, the claim holds. Therefore, the boundary of some face $`F`$ in $`\mathrm{\Phi }`$ intersects each of $`𝒢_i,𝒢_{i_1},\mathrm{},𝒢_i_{\mathrm{}}`$. Since $`F`$ must be unique, the boundary of $`F`$ intersects every set in $`𝒞_h`$ for every $`𝒞_h`$ in $``$ such that the sets in $`𝒞_h`$ fall into two or more of $`𝒢_i`$, $`𝒢_{i_1}`$, $`\mathrm{}`$, $`𝒢_i_{\mathrm{}}`$. Hence, the boundary of $`F`$ intersects every set in $`𝒰_j`$. Consequently, $`\mathrm{\Phi }_i`$ satisfies $`𝒰_{j,i}`$.

$`()`$ Let $`\mathrm{\Phi }_i`$ be an embedding of $`𝒢_i`$ satisfying $`_i`$. We construct an embedding of $`𝒢`$ satisfying $``$ as follows. First, consider a block $`B_j`$ of $`H`$. Let $`i_1,\mathrm{},i_{\mathrm{}}`$ be the vertices of $`B_j`$. Let $`𝒢_j^{}`$ be the subgraph of $`𝒢`$ formed by $`𝒢_{i_1}`$, …, $`𝒢_i_{\mathrm{}}`$. Let $`_j^{}`$ be the sequence consisting of $`𝒰_j`$ and the $`𝒢_{i_x}`$-local families in $``$ for $`x=1,\mathrm{},\mathrm{}`$. We can assume that the boundary of the exterior face of $`\mathrm{\Phi }_{i_x}`$ intersects every set in $`𝒰_{j,i_x}`$. By identifying the exterior faces of $`\mathrm{\Phi }_{i_1}`$, …, $`\mathrm{\Phi }_i_{\mathrm{}}`$, we can combine the embeddings into an embedding $`\mathrm{\Phi }_j^{}`$ of $`𝒢_j^{}`$ satisfying $`_j^{}`$. Next, we utilize $`T=\mathrm{\Psi }(H)`$ to combine $`\mathrm{\Phi }_1^{}`$, …, $`\mathrm{\Phi }_p^{}`$ into a single embedding of $`𝒢`$. First, root $`T`$ at a block of $`H`$. For a leaf $`B_{j_1}`$ in $`T`$, let $`𝒢_i`$ and $`B_{j_2}`$ be the parent and grandparent of $`B_{j_1}`$ in $`T`$, respectively. Let $`_{i,1}`$ (respectively, $`_{i,2}`$) be the restriction of $`\mathrm{\Phi }_{j_1}^{}`$ (respectively, $`\mathrm{\Phi }_{j_2}^{}`$) to $`𝒢_i`$. Note that $`\mathrm{\Phi }_i`$, $`_{i,1}`$, and $`_{i,2}`$ are topologically equivalent up to the choice of their exterior face. Thus, $`\mathrm{\Phi }_{j_1}^{}`$ (respectively, $`\mathrm{\Phi }_{j_2}^{}`$) can be obtained as follows: For every vertex $`i^{}i`$ of $`B_{j_1}`$ (respectively, $`B_{j_2}`$), put a suitable embedding $`_i^{}`$ of $`𝒢_i^{}`$ that is topologically equivalent to $`\mathrm{\Phi }_i^{}`$ into a suitable face $`F_i^{}`$ of $`\mathrm{\Phi }_i`$. This gives an embedding of those $`𝒢_x\{𝒢_1,\mathrm{},𝒢_k\}`$ with $`x𝒱(B_{j_1})𝒱(B_{j_2})`$. We replace $`\mathrm{\Phi }_{j_2}^{}`$ with this embedding, replace $`B_{j_2}`$ with the union of $`B_{j_1}`$ and $`B_{j_2}`$, and delete $`B_{j_1}`$ from $`T`$. Afterwards, if $`𝒢_i`$ becomes a leaf of $`T`$, then we further delete it from $`T`$. We repeat this process until $`T`$ is a single vertex, at which time we obtain an embedding of $`𝒢`$ satisfying $``$.

###### Theorem 4.3

Theorem 2.2 holds if it holds for Case M1.

Proof.  The proof follows from Lemma 4.2 and the fact that $`H`$ and the sequences $`_i`$ above can be constructed from $`𝒢`$ and $``$ in $`O(I)`$ time.

## 5 Reducing Case M1 to Case M2 where $`𝒢`$ is biconnected.

This section assumes Case M1 where $`𝒢`$ is connected. We also assume that $`𝒢`$ has at least two vertices; otherwise, the problem is trivial.

Section 5.1 shows how to eliminate one cut vertex from $`𝒢`$; iterating this elimination until $`𝒢`$ has no cut vertex gives us a reduction from Case M1 to Case M2. However, this reduction is not efficient. Section 5.2 describes a more efficient reduction based on a direct elimination of all cut vertices from $`𝒢`$. Throughout the rest of this section, let $`𝒞_1,\mathrm{},𝒞_q`$ be the families in $``$.

### 5.1 Eliminating one cut vertex

Let $`w`$ be a cut vertex of $`𝒢`$. Let $`W_1`$, …, $`W_k`$ be the vertex sets of the connected components of $`𝒢\{w\}`$. Let $`𝒢_i`$ be the subgraph of $`𝒢`$ induced by $`\{w\}W_i`$. $`𝒢_1,\mathrm{},𝒢_k`$ are called the augmented components induced by $`w`$. For each $`𝒞_h`$ in $``$, let $`U_{h,1}`$, …, $`U_{h,t_h}`$ be the sets in $`𝒞_h`$ containing $`w`$; possibly $`t_h=0`$. $`𝒞_h`$ is $`w`$-global if for all $`i\{1,\mathrm{},k\}`$, $`𝒞_h\{U_{h,1},\mathrm{},U_{h,t_h}\}`$ is not $`𝒢_i`$-local; otherwise, $`𝒞_h`$ is $`w`$-local.

###### Observation 5.1

1. Assume that $`𝒞_h\{U_{h,1},\mathrm{},U_{h,t_h}\}`$ is $`𝒢_i`$-local for some $`𝒢_i`$. Then, $`𝒢`$ satisfies $``$ if and only if $`𝒢`$ satisfies $``$ with $`𝒞_h`$ replaced by $`(𝒞_h\{U_{h,1},\mathrm{},U_{h,t_h}\})`$ $``$ $`\{U_{h,1}𝒱(𝒢_i)`$,…,$`U_{h,t_h}𝒱(𝒢_i)\}`$.
2. Assume that $`𝒞_h`$ is $`w`$-global. Then, $`𝒢`$ satisfies $``$ if and only if $`𝒢`$ satisfies $``$ with $`𝒞_h`$ replaced by $`𝒞_h\{U_{h,1},\mathrm{},U_{h,t_h}\}`$.

By Observation 5.1, we may assume that (1) each set in a $`w`$-global family in $``$ does not contain $`w`$ and (2) each set in a family in $``$ is $`𝒢_i`$-local for some $`𝒢_i`$. Let $`H`$ be an edge-labeled graph constructed as follows. The vertices of $`H`$ are $`1,\mathrm{},k`$. For each $`w`$-global family $`𝒞_h`$, $`H`$ has a cycle $`C`$ possibly of length 2 where (1) the vertices of $`C`$ are those $`i\{1,\mathrm{},k\}`$ such that at least one set in $`𝒞_h`$ is $`𝒢_i`$-local and (2) the edges of $`C`$ are all labeled $`h`$. See Figures 5(1) through 5(3) for an example of $`𝒢`$, $``$ and $`H`$.

Note that Observation 4.1 still holds for this $`H`$ and the augmented components $`𝒢_1,\mathrm{},𝒢_k`$. Thus, we may assume that $`H`$ is connected. Let $`B_1`$, $`\mathrm{}`$, $`B_p`$ be the blocks of $`H`$. Clearly, for each $`w`$-global family $`𝒞_h`$, exactly one block of $`H`$ contains all the edges labeled $`h`$. For each $`B_j`$, let $`𝒰_j=_h𝒞_h\{\{w\}\}`$ where $`h`$ ranges over all labels on the edges of $`B_j`$. For each $`𝒢_i`$, let $`_i`$ be the sequence consisting of the $`𝒢_i`$-local families in $``$ as well as the families $`𝒰_{j,i}=\{U𝒰_j|U`$ is $`𝒢_i`$-local} for all $`B_j`$ with $`i𝒱(B_j)`$. See Figure 5(4) for an example of $`_1,\mathrm{},_4`$ constructed from $`𝒢`$, $``$ and $`H`$ in Figures 5(1) through 5(3).

###### Lemma 5.2

$`𝒢`$ satisfies $``$ if and only if every $`𝒢_i`$ satisfies $`_i`$.

Proof.  The two directions are proved as follows.

$`()`$ The proof is the same as that of Lemma 4.2 except that the claim therein now implies that the boundary of some face $`F`$ in $`\mathrm{\Phi }`$ intersects each of $`𝒢_i\{w\},𝒢_{i_1}\{w\},\mathrm{},𝒢_i_{\mathrm{}}\{w\}`$.

$`()`$ The proof is the same as that of Lemma 4.2 except that $`\mathrm{\Phi }_{j_1}^{}`$ (respectively, $`\mathrm{\Phi }_{j_2}^{}`$) now can be obtained as follows: For each vertex $`i^{}i`$ of $`B_{j_1}`$ (respectively, $`B_{j_2}`$), put a suitable embedding $`_i^{}`$ of $`𝒢_i^{}`$ that is topologically equivalent to $`\mathrm{\Phi }_i^{}`$ into a suitable face $`F_i^{}`$ of $`\mathrm{\Phi }_i`$, and then identify the two occurrences of $`w`$.

### 5.2 Eliminating all cut vertices

Let $`T=\mathrm{\Psi }(𝒢)`$. A block vertex of $`T`$ is a vertex of $`T`$ that is a block of $`𝒢`$. Root $`T`$ at a block vertex and perform a post-order traversal of $`T`$. For each vertex $`\gamma `$ of $`T`$, let $`\mathrm{post}(\gamma )`$ be the post-order number of $`\gamma `$ in the post-order traversal of $`T`$.

Let $`W=\{w_1,\mathrm{},w_{\mathrm{}}\}`$ be the set of cut vertices of $`𝒢`$ where $`\mathrm{post}(w_1)<\mathrm{}<\mathrm{post}(w_{\mathrm{}})`$. For each $`v𝒱(𝒢)W`$, let $`\mathrm{post}(v)=\mathrm{post}(B)`$, where $`B`$ is the unique block of $`𝒢`$ with $`v𝒱(B)`$. We may assume $`𝒱(𝒢)=\{1,\mathrm{},n\}`$. For each $`v𝒱(𝒢)`$, the rank of $`v`$, denoted by $`\mathrm{rank}(v)`$, is $`(\mathrm{post}(v),v)`$. The rank of a vertex $`u`$ is lower than that of another vertex $`v`$ if (1) $`\mathrm{post}(u)<\mathrm{post}(v)`$ or (2) $`\mathrm{post}(u)=\mathrm{post}(v)`$ and $`u<v`$. For each $`w_iW`$, let $`B_{i,1}`$, …, $`B_{i,k_i}`$ be the children of $`w_i`$ in $`T`$. Let $`B_{i,0}`$ be the parent of vertex $`w_i`$ in $`T`$.

###### Theorem 5.3

Theorem 2.2 holds for Case M1 if it holds for Case M2.

Proof.  It suffices to construct a sequence $`[B]`$ for each block $`B`$ of $`𝒢`$, with a total size of $`O(I)`$ in $`O(I\mathrm{log}I)`$ total time over all the blocks of $`𝒢`$, such that $`𝒢`$ satisfies $``$ if and only if every $`B`$ satisfies $`[B]`$. To construct $`[B]`$ based on Observation 5.1 and Lemma 5.2, we process $`w_1`$, …, $`w_{\mathrm{}}`$ one at a time. During the processing of $`w_i`$, we construct $`[B_{i,j}]`$ for all $`j=1,\mathrm{},k_i`$. Then, we delete $`w_i`$, $`B_{i,1}`$, …, $`B_{i,k_i}`$ from $`T`$. After processing $`w_{\mathrm{}}`$, we are left with the root $`B_{\mathrm{},0}`$ for which we then construct $`[B_{\mathrm{},0}]`$.

We use the following data structures. See Figure 6 for an example of some of the data structures before processing the first cut vertex of $`𝒢`$.

1. During the construction, some families in $``$ may be united, and we use a union-find data structure to maintain a collection of disjoint dynamic subsets of $`\mathrm{\Delta }=\{1,\mathrm{},q\}`$. (Recall that $`q`$ is the number of families in $``$.) Each subset of $`\mathrm{\Delta }`$ in the data structure is identified by a representative member of the subset. For each $`h\mathrm{\Delta }`$, let $`R(h)`$ be the representative of the subset containing $`h`$. Initially, each $`h\mathrm{\Delta }`$ forms a singleton subset, and thus, $`R(h)=h`$.
2. Each set $`U`$ in a family in $``$ is implemented as a pair $`(𝒲[U],𝒮[U])`$, where $`𝒲[U]`$ is a linked list, and $`𝒮[U]`$ is a splay tree . Initially, $`𝒲[U]`$ consists of the vertices in $`UW`$ in the increasing order of their post-order numbers. $`𝒮[U]`$ is initialized by inserting the ranks of the vertices in $`UW`$ into an empty splay tree. A splay tree supports the following operations in amortized logarithmic time per operation: (1) insert a rank and (2) delete the ranks in a given range.
3. A linked list $`L[B]`$, for each block $`B`$ of $`𝒢`$. Initially, each $`L[B]`$ consists of all pairs $`(h,U)`$ such that $`h\mathrm{\Delta }`$, $`U𝒞_h`$, $`U`$ is $`B`$-local, and $`UW=\mathrm{}`$.
4. A linked list $`L[w_i]`$, for each $`w_iW`$. Initially, each $`L[w_i]`$ consists of all pairs $`(h,U)`$ such that $`h\mathrm{\Delta }`$, $`U𝒞_h`$, $`w_iU`$, and $`i=\mathrm{min}\{j|w_jUW\}`$.
5. An array $`A_1[1..q]`$ of integers. Initially, for each $`h\mathrm{\Delta }`$, $`A_1[h]=\mathrm{max}_\gamma \mathrm{post}(\gamma )`$ where $`\gamma `$ ranges over all vertices of $`T`$ such that $`L[\gamma ]`$ contains a pair $`(h,)`$ with $``$ = “don’t care”.
6. An array $`A_2[1..q]`$ of integers. Initially, for each $`h\mathrm{\Delta }`$, $`A_2[h]=0`$.
7. An array $`J[1..q]`$ of linked lists of integers. Initially, for each $`h\mathrm{\Delta }`$, $`J[h]`$ is empty.
8. A temporary array $`Y[1..q]`$ of integers.

We maintain the following invariants immediately before processing each $`w_i`$. In particular, we initialize the above data structures so that the invariants hold before $`w_1`$ is processed. It takes $`O(I)`$ total time to initialize the data structures except the splay trees.

1. For each vertex $`\gamma `$ of $`T`$ and each pair $`(h,U)L[\gamma ]`$, (1) $`𝒲[U]`$ consists of the vertices in $`U\{w_i,\mathrm{},w_{\mathrm{}}\}`$ in the increasing order of their post-order numbers, (2) the rank of each vertex of $`U\{w_i,\mathrm{},w_{\mathrm{}}\}`$ is stored in $`𝒮[U]`$, and (3) for every $`w_jU\{w_1,\mathrm{},w_{i1}\}`$, $`\mathrm{post}(w_j)`$ and $`\mathrm{rank}(w_j)`$ have been updated as $`\mathrm{post}(B_{j,0})`$ and $`(\mathrm{post}(B_{j,0}),w_j)`$, respectively.
2. For each block vertex $`B`$ of $`T`$ and each $`(h,U)L[B]`$, it holds that $`h\mathrm{\Delta }`$, $`U`$ is $`B`$-local, and $`U\{w_i,\mathrm{},w_{\mathrm{}}\}=\mathrm{}`$.
3. For each $`j\{i,\mathrm{},\mathrm{}\}`$ and each $`(h,U)L[w_j]`$, it holds that $`h\mathrm{\Delta }`$, $`w_jU`$, and $`j=\mathrm{min}\{x|ix\mathrm{}`$ and $`w_xU\}`$.
4. For each $`h\mathrm{\Delta }`$ with $`R(h)=h`$, let $`𝒞_h^{}=\{U|`$ there is a vertex $`\gamma `$ of $`T`$ such that $`L[\gamma ]`$ contains a pair $`(h^{},U)`$ with $`R(h^{})=h\}`$. Let $`^{}`$ be the sequence of all families $`𝒞_h^{}`$ such that $`h\mathrm{\Delta }`$ and $`R(h)=h`$. Let $`𝒢^{}`$ be the subgraph of $`𝒢`$ induced by $`_B𝒱(B)`$, where $`B`$ ranges over all the block vertices of $`T`$. Then, $`𝒢`$ satisfies $``$ if and only if (1) $`𝒢^{}`$ satisfies $`^{}`$ and (2) for each block $`B`$ of $`𝒢`$ that has been deleted from $`T`$, $`B`$ satisfies $`[B]`$.
5. For each $`h\mathrm{\Delta }`$ with $`R(h)=h`$, $`A_1[h]=\mathrm{max}_\gamma \mathrm{post}(\gamma )`$ where $`\gamma `$ ranges over all vertices of $`T`$ such that $`L[\gamma ]`$ contains a pair $`(h^{},)`$ with $`R(h^{})=h`$.
6. For each $`h\mathrm{\Delta }`$, $`A_2[h]=0`$ and $`J[h]`$ is empty.

We process $`w_i`$ in the following stages W1 through W4. See Figure 7 for an example of some of the data structures after processing the first cut vertex of $`𝒢`$.

$``$ Stage W1 checks whether each related family is $`w_i`$-global as follows.

1. Compute $`X=\{h\mathrm{\Delta }|R(h)=h`$, and for some $`j\{1,\mathrm{},k_i\}`$, $`L[B_{i,j}]`$ contains a pair $`(h^{},)`$ with $`R(h^{})=h\}`$. (Remark. For each $`h\mathrm{\Delta }X`$ with $`R(h)=h`$, the family $`𝒞_h^{}\{U|w_iU\}`$ is $`Q_i`$-local, where $`Q_i`$ is the augmented component of $`𝒢^{}`$ induced by $`w_i`$ that is not among $`B_{i,1}`$, …, $`B_{i,k_i}`$. See the fourth invariant for $`𝒞_h^{}`$ and $`𝒢^{}`$.)
2. For each $`hX`$, set $`Y[h]`$ to be the number of integers $`j\{1,\mathrm{},k_i\}`$ such that $`L[B_{i,j}]`$ contains a pair $`(h^{},)`$ with $`R(h^{})=h`$. (Remark. For $`hX`$, $`Y[h]1`$.)
3. For each $`hX`$, perform the following:

1. If $`Y[h]=1`$ and $`A_1[h]\mathrm{post}(w_i)`$, then set $`A_2[h]=j`$ where $`j`$ is the unique integer in $`\{1,\mathrm{},k_i\}`$ such that $`L[B_{i,j}]`$ contains a pair $`(h^{},)`$ with $`R(h^{})=h`$. (Remark. $`𝒞_h^{}\{U|w_iU\}`$ is $`B_{i,j}`$-local.)
    2. Otherwise set $`A_2[h]=1`$. (Remark. $`𝒞_h^{}\{U|w_iU\}`$ is $`w_i`$-global.)

$``$ Stage W2 modifies each $`U`$ with $`w_iU`$ in each $`w_i`$-local family based on Observation 5.1(1) as follows.

1. For each $`(h,U)L[w_i]`$ with $`A_2[R(h)]1`$, let $`j=A_2[R(h)]`$, delete all vertices outside $`𝒱(B_{i,j})`$ from $`U`$, and then insert $`(h,U)`$ to $`L[B_{i,j}]`$. Here, deleting all vertices outside $`𝒱(B_{i,j})`$ from $`U`$ is done as follows: Delete $`w_i`$ from $`𝒲[U]`$, delete all the ranks in the range $`[\mathrm{}..(\mathrm{post}(B_{i,j}),0)]`$ and all the ranks in the range $`[(\mathrm{post}(B_{i,j}),n+1)..\mathrm{}]`$ from $`𝒮[U]`$, and insert $`(\mathrm{post}(B_{i,j}),w_i)`$ to $`𝒮[U]`$.
2. For each $`(h,U)L[w_i]`$ with $`A_2[R(h)]=0`$, perform the following:
(Remark. $`𝒞_h^{}\{U|w_iU\}`$ is $`Q_i`$-local. See the remark in Step 1 of Stage W1 for $`Q_i`$.)

1. Delete all vertices $`v`$ with $`\mathrm{post}(v)<\mathrm{post}(w_i)`$ from $`U`$ as follows: Delete $`w_i`$ from $`𝒲[U]`$, delete all the ranks in the range $`[\mathrm{}..\mathrm{rank}(w_i)]`$ from $`𝒮[U]`$, and insert $`(\mathrm{post}(B_{i,0}),w_i)`$ to $`𝒮[U]`$.
    2. If $`𝒲[U]=\mathrm{}`$, i.e., $`U`$ has no cut vertex, then insert $`(h,U)`$ to $`L[B_{i,0}]`$ and set $`A_1[R(h)]=\mathrm{max}\{\mathrm{post}(B_{i,0}),A_1[R(h)]\}`$.
    3. If $`𝒲[U]\mathrm{}`$, then find the first vertex $`w_j`$ in $`𝒲[U]`$, insert $`(h,U)`$ to $`L[w_j]`$, and set $`A_1[R(h)]=\mathrm{max}\{\mathrm{post}(w_j),A_1[R(h)]\}`$. (Remark. $`j>i`$.)

$``$ Stage W3 modifies each $`w_i`$-global family based on Observation 5.1(2) as follows.

1. For each $`hX`$ with $`A_2[h]=1`$, set $`J[h]=\{j\{1,\mathrm{},k_i\}|L[B_{i,j}]`$ contains a pair $`(h^{},)`$ with $`R(h^{})=h\}`$.
2. For each $`hX`$ with $`A_2[h]=1`$ and $`A_1[h]>\mathrm{post}(w_i)`$, insert 0 to $`J[h]`$.
3. Set $`\mathrm{post}(w_i)=\mathrm{post}(B_{i,0})`$ and $`\mathrm{rank}(w_i)=(\mathrm{post}(B_{i,0}),w_i)`$.
4. Construct an edge-labeled graph $`H_i`$ as follows. The vertices of $`H_i`$ are $`0`$, $`1`$, …, $`k_i`$. For each $`hX`$ with $`A_2[h]=1`$, $`H_i`$ has a cycle possibly of length 2 whose vertices are the integers in $`J[h]`$ and whose edges are all labeled $`h`$.
5. For each block $``$ of $`H_i`$, find the labels $`h_1,\mathrm{},h_t`$ on the edges in $``$ and unite those subsets in the union-find data structure that have $`h_1,\mathrm{},h_t`$ as their representative, respectively; afterwards, for the representative $`h_r`$ of the resulting subset, further perform the following:

1. Insert $`(h_r,\{w_i\})`$ to all lists $`L[B_{i,j}]`$ such that $`j𝒱()`$.
    2. If $`0𝒱()`$, then set $`A_1[h_r]=\mathrm{max}\{\mathrm{post}(B_{i,0})`$, $`A_1[h_1]`$, …, $`A_1[h_t]\}`$.

$``$ Stage W4 constructs the sequences $`[B_{i,j}]`$ for $`1jk_i`$ and updates the data structures as follows.

1. For each $`j`$ and each $`(h,U)`$ in $`L[B_{i,j}]`$, replace $`(h,U)`$ by $`(R(h),U)`$.
2. For each $`j`$, set $`[B_{i,j}]`$ to be the sequence of the families $`𝒞_h^{\prime \prime }=\{U|(h,U)L[B_{i,j}]\}`$, where $`h`$ ranges over those integers that are in a pair in $`L[B_{i,j}]`$.
3. Delete $`w_i`$ and its children from $`T`$.
4. For each $`hX`$, set $`A_2[h]=0`$ and $`J[h]=\mathrm{}`$.

By Observation 5.1 and Lemma 5.2, after the processing of $`w_i`$, the invariants hold for $`i+1`$.

After processing $`w_{\mathrm{}}`$, we construct $`[B_{\mathrm{},0}]`$ as follows: Replace each pair $`(h,U)`$ in $`L[B_{\mathrm{},0}]`$ by $`(R(h),U)`$, and then set $`[B_{\mathrm{},0}]`$ to be the sequence of the families $`𝒞_h^{\prime \prime }=\{U|(h,U)L[B_{\mathrm{},0}]\}`$, where $`h`$ ranges over those integers that are in a pair in $`L[B_{\mathrm{},0}]`$.

By the invariants, Observation 5.1, and Lemma 5.2, $`𝒢`$ satisfies $``$ if and only if every block $`B`$ of $`𝒢`$ satisfies $`[B]`$. As for the time complexity, we make the following observations:

1. When processing $`w_i`$, we create at most $`n_i`$ new sets all equal to $`\{w_i\}`$, where $`n_i`$ is the maximum number of blocks in a simple graph with $`k_i+1`$ vertices. Since $`n_i=O(k_i+1)`$ and $`k_i+1`$ does not exceed the degree of $`w_i`$ in $`𝒢`$, the total number of newly created sets is $`O(|𝒢|)`$.
2. If a set $`U`$ does not intersect $`\{w_i,\mathrm{},w_{\mathrm{}}\}`$ immediately before the processing of $`w_i`$, then there is at most one $`w_j\{w_i,\mathrm{},w_{\mathrm{}}\}`$ such that some vertices of $`U`$ are touched during the processing of $`w_j`$.
3. If $`w_i`$ is in $`U`$ immediately before the processing of $`w_i`$, then we either (1) touch at most $`1+|\{vU|\mathrm{post}(v)\mathrm{post}(w_i)\}|`$ vertices of $`U`$ during the processing of $`w_i`$, or (2) touch no vertex of $`U`$ during the processing of each $`w_j\{w_{i+1},\mathrm{},w_{\mathrm{}}\}`$.

There are at most $`q`$ unions and $`O(I)`$ finds, and at most $`|𝒢|`$ insertions into each splay tree. By the above observations, the total time spent on the union-find data structure is $`O(I\mathrm{log}I)`$, that on the splay trees is $`O(I\mathrm{log}|𝒢|)`$, and that on the remaining computation is $`O(I)`$, all within the desired time.

## 6 Case M2 where $`𝒢`$ is biconnected.

This section assumes that $`𝒢`$ is biconnected. Let $`𝒞_1,\mathrm{},𝒞_q`$ be the families in $``$. For each $`i\{1,\mathrm{},q\}`$, let $`𝒞_i=\{U_{i,1},\mathrm{},U_{i,r_i}\}`$.

###### Theorem 6.1

Theorem 2.2 holds for Case M2.

To prove Theorem 6.1, we review a decomposition of $`𝒢`$ in §6.1, outline the basic ideas of our CFE algorithm in §6.2, detail the algorithm in §6.3, and analyze it in §6.4.

### 6.1 SPQR decompositions

A planar $`st`$-graph $`G`$ is a directed acyclic plane graph such that $`G`$ has exactly one source $`s`$ and exactly one sink $`t`$, and both vertices are on the exterior face. These two vertices are the poles of $`G`$. A split pair of $`G`$ is either a pair of adjacent vertices or a pair of vertices whose removal disconnects the graph obtained from $`G`$ by adding the edge $`(s,t)`$. A split component of a split pair $`\{u,v\}`$ is either an edge $`(u,v)`$ or a maximal subgraph $`C`$ of $`G`$ such that $`C`$ is a planar $`uv`$-graph and $`\{u,v\}`$ is not a split pair of $`C`$. A split pair $`\{u,v\}`$ of $`G`$ is maximal if there is no other split pair $`\{u^{},v^{}\}`$ in $`G`$ such that a split component of $`\{u^{},v^{}\}`$ contains both $`u`$ and $`v`$.

The decomposition tree $`T`$ of $`G`$ is a rooted ordered tree recursively defined in four cases as follows. The nodes of $`T`$ are of four types $`S,P,Q`$, and $`R`$. Each node $`\mu `$ of $`T`$ has an associated planar $`st`$-graph $`\mathrm{ske}(\mu )`$, called the skeleton of $`\mu `$. Also, $`\mu `$ is associated with an edge in the skeleton of the parent $`\varphi `$ of $`\mu `$, called the virtual edge of $`\mu `$ in $`\mathrm{ske}(\varphi )`$.

Case Q: $`G`$ is a single edge from $`s`$ to $`t`$. Then, $`T`$ is a Q-node whose skeleton is $`G`$.

Case S: $`G`$ is not biconnected. Let $`c_1,\mathrm{},c_{k1}`$ with $`k2`$ be the cut vertices of $`G`$. Since $`G`$ is a planar $`st`$-graph, each $`c_i`$ is in exactly two blocks $`G_i`$ and $`G_{i+1}`$ with $`sG_1`$ and $`tG_k`$. Then, $`T`$’s root is an S-node $`\mu `$, and $`\mathrm{ske}(\mu )`$ consists of the chain $`e_1,\mathrm{},e_k`$, where the edge $`e_i`$ goes from $`c_{i1}`$ to $`c_i`$, $`c_0=s`$, and $`c_k=t`$.

Case P: $`\{s,t\}`$ is a split pair of $`G`$ with $`k`$ split components where $`k2`$. Then, $`T`$’s root is a P-node $`\mu `$, and $`\mathrm{ske}(\mu )`$ consists of $`k`$ parallel edges $`e_1,\mathrm{},e_k`$ from $`s`$ to $`t`$.

Case R: Otherwise. Let $`\{s_1,t_1\},\mathrm{},\{s_k,t_k\}`$ with $`k1`$ be the maximal split pairs of $`G`$. Let $`G_i`$ be the union of the split components of $`\{s_i,t_i\}`$. Then, $`T`$’s root is an R-node $`\mu `$, and $`\mathrm{ske}(\mu )`$ is the simple graph obtained from $`G`$ by replacing each $`G_i`$ with an edge $`e_i`$ from $`s_i`$ to $`t_i`$. Note that adding the edge $`(s,t)`$ to $`\mathrm{ske}(\mu )`$ yields a simple triconnected graph.

Figure 8 illustrates the decomposition tree of $`G`$ as well as the skeletons of $`\mu `$ and $`\nu `$. In the last three cases, $`\mu `$ has children $`\chi _1,\mathrm{},\chi _k`$ in this order, such that each $`\chi _i`$ is the root of the decomposition tree of $`G_i`$. The virtual edge of $`\chi _i`$ is the edge $`e_i`$ in $`\mathrm{ske}(\mu )`$. $`G_i`$ is called the pertinent graph $`\mathrm{pert}(\chi _i)`$ of $`\chi _i`$ as well as the expansion graph of $`e_i`$. Note that $`G`$ is the pertinent graph of $`T`$’s root. Also, no child of an S-node is an S-node, and no child of a P-node is a P-node.

The allocation nodes of a vertex $`v`$ of $`G`$ are the nodes of $`T`$ whose skeleton contains $`v`$; note that $`v`$ has at least one allocation node.

###### Lemma 6.2 (see )

1. $`T`$ has $`O(|G|)`$ nodes and can be constructed in $`O(|G|)`$ time. The total number of edges of the skeletons stored at the nodes of $`T`$ is $`O(|G|)`$.
2. The pertinent graphs of the children of $`\mu `$ can only share vertices of $`\mathrm{ske}(\mu )`$.
3. If $`v`$ is in $`\mathrm{ske}(\mu )`$, then $`v`$ is also in the pertinent graph of all ancestors of $`\mu `$.
4. If $`v`$ is a pole of $`\mathrm{ske}(\mu )`$, then $`v`$ is also in the skeleton of the parent of $`\mu `$. If $`v`$ is in $`\mathrm{ske}(\mu )`$ but is not a pole of $`\mathrm{ske}(\mu )`$, then $`v`$ is not in the skeleton of any ancestor of $`\mu `$.
5. The least common ancestor $`\mu `$ of the allocation nodes of $`v`$ itself is an allocation node of $`v`$, called the proper allocation node of $`v`$. Also, if $`v\{s,t\}`$, then $`\mu `$ is the only allocation node of $`v`$ such that $`v`$ is not a pole of $`\mathrm{ske}(\mu )`$.
6. If $`vs,t`$, then the proper allocation node of $`v`$ is an R-node or S-node.

For each non-S-node $`\mu `$ in $`T`$, $`\mathrm{pert}(\mu )`$ is called a block of $`G`$ , which differs from that in §4 and §5. For a block $`B=\mathrm{pert}(\mu )`$, let $`\mathrm{node}(B)=\mu `$. For an ancestor $`\varphi `$ of $`\mathrm{node}(B)`$, the representative of $`B`$ in $`\mathrm{ske}(\varphi )`$ is the edge in $`\mathrm{ske}(\varphi )`$ whose expansion graph contains $`B`$.

Let $`\mu `$ be an R-node or P-node in $`T`$ with children $`\chi _1,\mathrm{},\chi _b`$. For each $`k\{1,\mathrm{},b\}`$, let $`e_k`$ be the virtual edge of $`\chi _k`$ in $`\mathrm{ske}(\mu )`$. If $`\chi _k`$ is an S-node, $`\mathrm{pert}(\chi _k)`$ is a chain consisting of two or more blocks. If $`\chi _k`$ is an R-node or P-node, $`\mathrm{pert}(\chi _k)`$ is a single block. For each $`k\{1,\mathrm{},b\}`$, we say that the blocks in $`\mathrm{pert}(\chi _k)`$ are on edge $`e_k`$. The minor blocks of $`\mathrm{pert}(\mu )`$ are the blocks on $`e_1`$, …, the blocks on $`e_b`$.

### 6.2 Basic ideas

An $`st`$-orientation of a planar graph is an orientation of its edges together with an embedding such that the resulting digraph is a planar $`st`$-graph.

###### Lemma 6.3 (see )

If an $`n`$-vertex simple planar graph has an $`st`$-orientation, then every embedding, where $`s`$ and $`t`$ are on the exterior face, of this graph can be obtained from this orientation through a sequence of $`O(n)`$ following operations:

1. Flip an R-node’s skeleton around its poles.
2. Permute a P-node’s children (and consequently their skeletons with respect to their common poles).

Let $`\{s,t\}`$ be an edge of $`𝒢`$. Since $`𝒢`$ is a simple biconnected graph, we convert $`𝒢`$ to a planar $`st`$-graph in $`O(n)`$ time  for technical convenience. For the remainder of §6, let $`T`$ be the decomposition tree of $`𝒢`$.

The CFE algorithm processes the nodes of $`T`$ in a bottom-up manner. It first processes the leaf nodes of $`T`$. When processing a node $`\mu `$, for each $`𝒞_i`$ such that $`\mathrm{pert}(\mu )`$ is the smallest block that intersects every set in $`𝒞_i`$, the algorithm looks for an embedding of $`\mathrm{pert}(\mu )`$ that satisfies $`𝒞_i`$. If this is impossible, the algorithm outputs “no” and stops; otherwise, it continues on to process the next node of $`T`$. We note, in passing, that Theorem 3.8(2) is used when processing R-nodes.

Let $`\mu `$ be a node of $`T`$. $`T_\mu `$ denotes the subtree of $`T`$ rooted at $`\mu `$ and $`0pt(\mu )`$ denotes the distance from $`T`$’s root to $`\mu `$. We need the following definitions:

1. $`U_{i,j}`$ is contained in $`\mathrm{pert}(\mu )`$ if the vertices of $`U_{i,j}`$ are all in $`\mathrm{pert}(\mu )`$; $`U_{i,j}`$ is strictly contained in $`\mathrm{pert}(\mu )`$ if in addition, no pole of $`\mathrm{pert}(\mu )`$ is in $`U_{i,j}`$.
2. Let $`\mathrm{done}(U_{i,j})`$ be the deepest node $`\mu `$ in $`T`$ such that $`U_{i,j}`$ is strictly contained in $`\mathrm{pert}(\mu )`$, if such a node exists. If no such $`\mu `$ exists, then $`U_{i,j}`$ contains a pole of $`𝒢`$ and let $`\mathrm{done}(U_{i,j})`$ be $`T`$’s root.
3. A family $`𝒞_i`$ straddles $`\mathrm{pert}(\mu )`$ if at least one set in $`𝒞_i`$ is strictly contained in $`\mathrm{pert}(\mu )`$, and at least one set in $`𝒞_i`$ has no vertex in $`\mathrm{pert}(\mu )`$.
4. Let $`\mathrm{done}(𝒞_i)`$ be the deepest node $`\mu `$ in $`T`$ such that for every $`U_{i,j}𝒞_i`$, at least one vertex of $`U_{i,j}`$ is in $`\mathrm{pert}(\mu )`$.
5. Let $`\mathrm{sub}(\mu )=\{U_{i,j}|\mathrm{done}(U_{i,j})=\mu \}`$ and $`\mathrm{fam}(\mu )=\{𝒞_i|\mathrm{done}(𝒞_i)=\mu \}`$.
6. If $`\mu `$ is a P-node or R-node, let $`\mathrm{xfam}(\mu )=\mathrm{fam}(\mu )(_{\chi _k}\mathrm{fam}(\chi _k))`$ and $`\mathrm{xsub}(\mu )=\mathrm{sub}(\mu )(_{\chi _k}\mathrm{sub}(\chi _k))`$, where $`\chi _k`$ ranges over all S-children of $`\mu `$.

In a fixed embedding of a block $`B`$, the poles of $`B`$ divide the boundary of its exterior face into two paths $`\mathrm{side}_1(B)`$ and $`\mathrm{side}_2(B)`$, called the two sides of $`B`$. $`U_{i,j}`$ is two-sided for $`B`$ if both $`\mathrm{side}_1(B)`$ and $`\mathrm{side}_2(B)`$ intersect $`U_{i,j}`$. In particular, $`U_{i,j}`$ is two-sided for $`B`$ if it contains a pole of $`B`$. $`U_{i,j}`$ is side-1 (respectively, side-2) for $`B`$ if only $`\mathrm{side}_1(B)`$ (respectively, $`\mathrm{side}_2(B)`$) intersects $`U_{i,j}`$. Assume that $`B`$ is a minor block of $`\mathrm{pert}(\mu )`$ for some $`\mu `$. Let $`e_k`$ be the representative of $`B`$ in $`\mathrm{ske}(\mu )`$. In a fixed embedding of $`\mathrm{ske}(\mu )`$, $`e_k`$ separates two faces $`F`$ and $`F^{}`$. When embedding $`\mathrm{pert}(\mu )`$, we can embed $`\mathrm{side}_1(B)`$ towards either $`F`$ or $`F^{}`$, referred to as the two orientations of $`B`$ in $`\mathrm{pert}(\mu )`$.

A family $`𝒞_i`$ is side-0 (respectively, side-1 or side-2) exterior-forcing for $`B`$ if $`\mathrm{done}(𝒞_i)`$ is an ancestor of $`\mathrm{node}(B)`$ in $`T`$ and some $`U_{i,j}𝒞_i`$ strictly contained in $`B`$ is two-sided (respectively, side-1 or side-2) for $`B`$. For $`p=0`$, 1, 2, define

1. $`\mathrm{ext}_p(B)=`$ $`\mathrm{min}\{0pt(\mathrm{done}(𝒞_i))|𝒞_i`$, $`1iq`$, is side-$`p`$ exterior-forcing for $`B\}`$, if at least one family in $``$ is side-$`p`$ exterior-forcing for $`B`$;
2. $`\mathrm{ext}_p(B)=\mathrm{}`$ otherwise.

Assume $`\mathrm{ext}_p(B)\mathrm{}`$. Let $`\mu =\mathrm{node}(B),\varphi _1,\varphi _2,\mathrm{},\varphi _h`$ be the path in $`T`$ from $`\mu `$ to $`\varphi _h`$, where $`0pt(\varphi _h)=\mathrm{ext}_p(B)`$. For each $`\mathrm{}\{1,\mathrm{},h1\}`$, the representative of $`B`$ in $`\mathrm{ske}(\varphi _{\mathrm{}})`$ must be an exterior edge in any satisfying embedding of $`\mathrm{ske}(\varphi _{\mathrm{}})`$. In addition, if $`p=1`$ or 2, $`\mathrm{side}_p(B)`$ must be embedded towards the exterior face of the embedding of $`\mathrm{pert}(\varphi _{\mathrm{}})`$.

Since $`(s,t)`$ is an edge of $`𝒢`$, the root $`\rho `$ of $`T`$ is a P-node and has a child Q-node $`\varphi `$ representing $`(s,t)`$. A subtle difference between $`\rho `$ and each non-root node of $`T`$ is that the two sides of $`𝒢=\mathrm{pert}(\rho )`$ is actually on the same face. To eliminate this difference, we delete $`\varphi `$ from $`T`$; afterwards, if $`\rho `$ has only one child, we further delete $`\rho `$ from $`T`$. From here onwards, $`T`$ denotes this modified tree.

### 6.3 The CFE algorithm

The CFE algorithm processes $`T`$ from bottom up. A ready node $`\mu `$ of $`T`$ is either (1) a leaf node or (2) a P-node or R-node such that the non-S-children of $`\mu `$ and the children of every S-child of $`\mu `$ all have been processed. The CFE algorithm processes the ready nodes of $`T`$ in an arbitrary order. An S-node is processed when its parent is processed. We detail how to process $`\mu `$ as follows.

For the case where $`\mu `$ is a leaf node of $`T`$, note that $`\mathrm{pert}(\mu )`$ is a single edge of $`𝒢`$. Since no $`U_{i,j}`$ is strictly contained in $`\mathrm{pert}(\mu )`$, $`\mathrm{sub}(\mu )=\mathrm{}`$. Also, each $`𝒞_i\mathrm{fam}(\mu )`$ is satisfied by every embedding of $`𝒢`$. Therefore, we simply set $`\mathrm{ext}_p(\mathrm{pert}(\mu ))=\mathrm{}`$ for $`p=0,1,2`$.

We next consider the case where $`\mu `$ is a non-leaf ready node. Before $`\mu `$ is processed, an embedding of every minor block of $`\mathrm{pert}(\mu )`$ is already fixed, except for a possible flip around its poles. Moreover, for each minor block $`B`$ of $`\mathrm{pert}(\mu )`$ and each $`p\{0,1,2\}`$, $`\mathrm{ext}_p(B)`$ is known. When processing $`\mu `$, the CFE algorithm checks whether some embedding $`\mathrm{\Phi }_\mu `$ of $`\mathrm{pert}(\mu )`$ satisfies the following two conditions:

1. $`\mathrm{\Phi }_\mu `$ satisfies every $`𝒞_i`$ in $`\mathrm{xfam}(\mu )`$.
2. For each $`𝒞_i`$ straddling $`\mathrm{pert}(\mu )`$ and each $`U_{i,j}𝒞_i`$ strictly contained in $`\mathrm{pert}(\mu )`$, at least one vertex of $`U_{i,j}`$ is embedded on the exterior face of $`\mathrm{\Phi }_\mu `$. (Remark. This ensures the existence of an embedding of $`\mathrm{pert}(\mathrm{done}(𝒞_i))`$ satisfying $`𝒞_i`$ later.)

If no such $`\mathrm{\Phi }_\mu `$ exists, then $`𝒢`$ cannot satisfy $``$ and the CFE algorithm outputs “no” and stops. Otherwise, it finds such an $`\mathrm{\Phi }_\mu `$ and fixes it except for a possible flip around its poles. It also computes $`\mathrm{ext}_p(\mathrm{pert}(\mu ))`$ for $`p=0`$, 1, 2.

To detail how to process $`\mu `$, we classify the sets $`U_{i,j}`$ that intersect $`\mathrm{pert}(\mu )`$ into four types and define a set $`\mathrm{img}(U_{i,j},\mu )`$ for each type as follows.

Type 1: $`U_{i,j}`$ contains at least one pole of $`\mathrm{ske}(\mu )`$. Then, $`\mathrm{done}(U_{i,j})`$ is an ancestor of $`\mu `$. Let $`\mathrm{img}(U_{i,j},\mu )=\{vU_{i,j}|v`$ is a vertex in $`\mathrm{ske}(\mu )\}`$.

Type 2: $`U_{i,j}`$ contains at least one vertex but no pole of $`\mathrm{ske}(\mu )`$. Then, $`\mathrm{done}(U_{i,j})=\mu `$. Let $`\mathrm{img}(U_{i,j},\mu )`$ as in the case of type 1.

Type 3: $`U_{i,j}`$ is strictly contained in $`\mathrm{pert}(\chi )`$ for some S-node child $`\chi `$ of $`\mu `$ and $`U_{i,j}`$ contains at least one vertex in $`\mathrm{ske}(\chi )`$. Then, $`\mathrm{done}(U_{i,j})=\chi `$. Let $`\mathrm{img}(U_{i,j},\mu )`$ consist of the virtual edge of $`\chi `$ in $`\mathrm{ske}(\mu )`$.

Type 4: $`U_{i,j}`$ is strictly contained in a minor block $`B`$ of $`\mathrm{pert}(\mu )`$. Then, $`\mathrm{done}(U_{i,j})`$ is $`\mathrm{node}(B)`$ or its descendent. Let $`\mathrm{img}(U_{i,j},\mu )`$ consist of the representative of $`B`$ in $`\mathrm{ske}(\mu )`$.

Each element of $`\mathrm{img}(U_{i,j},\mu )`$ is called an image of $`U_{i,j}`$ in $`\mathrm{ske}(\mu )`$. The remainder of §6.3 details how to process $`\mu `$.

#### 6.3.1 Processing an S-child of $`\mu `$

When processing $`\mu `$, for each S-child $`\chi `$ of $`\mu `$, we need to find an embedding of $`\mathrm{pert}(\chi )`$ satisfying certain conditions. We call this process the S-procedure and describe it below.

Let $`\chi `$ be an S-child of $`\mu `$. Then, $`\mathrm{ske}(\chi )`$ is a path. Let $`e_1`$, …, $`e_b`$ be the edges in $`\mathrm{ske}(\chi )`$. For each $`k\{1,\mathrm{},b\}`$, let $`B_k`$ be the expansion graph of $`e_k`$. Before the S-procedure is called on $`\chi `$, the following requirements are met:

1. For each $`k\{1,\mathrm{},b\}`$, an embedding of $`B_k`$ has been fixed, except for a possible flip around its poles.
2. For some integers $`k\{1,\mathrm{},b\}`$ and $`p\{1,2\}`$, $`\mathrm{side}_p(B_k)`$ is required to face either the left or the right side of $`\mathrm{ske}(\chi )`$.

Our only choice for embedding $`\mathrm{pert}(\chi )`$ is to flip $`B_1`$, …, $`B_b`$ around their poles. We need to check whether for some combination of flippings of $`B_1`$, …, $`B_b`$, (1) the resulting embedding satisfies every $`𝒞_i\mathrm{fam}(\chi )`$ and (2) the second requirement above is met.

The S-procedure consists of the following five stages:

$``$ Stage S1 constructs an auxiliary graph $`D=(V_D,E_D)`$ with $`V_D=\{k_p|1kb,p=1,2\}`$ as follows. For each $`𝒞_i\mathrm{fam}(\chi )`$, insert an arbitrary path $`P_i`$ into $`D`$ to connect all $`k_pV_D`$ such that for some type-4 $`U_{i,j}𝒞_i`$, (a) $`\mathrm{img}(U_{i,j},\chi )=\{e_k\}`$ and (b) $`U_{i,j}`$ is side-$`p`$ for $`B_k`$. To avoid confusion, we call the elements of $`V_D`$ points, and the connected components of $`D`$ clusters. Those points $`k_pV_D`$ such that $`\mathrm{side}_p(B_k)`$ is required to face the left side of $`\mathrm{ske}(\chi )`$ are called $`L`$-points. R-points are defined similarly. Note that for each cluster $`C`$ of $`D`$, all $`\mathrm{side}_p(B_k)`$ where $`k_p`$ ranges over all the points in $`C`$ must be embedded toward the same side of $`\mathrm{ske}(\chi )`$. Also, each type-3 $`U_{i,j}`$ in $`𝒞_i`$ contains a vertex in $`\mathrm{ske}(\chi )`$ which is on both sides of $`\mathrm{ske}(\chi )`$. For this reason, such sets were not considered when constructing $`D`$.

$``$ Stage S2 checks whether there is a cluster of $`D`$ containing both an $`L`$-point and an R-point. If such a cluster exists, then S2 outputs “no” and stops. Suppose that no such cluster exists. If a cluster $`C`$ contains an $`L`$-point (respectively, $`R`$-point), we call $`C`$ an $`L`$-cluster (respectively, $`R`$-cluster).

$``$ Stage S3 constructs another auxiliary graph $`RD=(V_{RD},E_{RD})`$ from $`D`$ as follows. The vertices of $`RD`$ are the clusters of $`D`$. For each $`k\{1,\mathrm{},b\}`$, there is an edge $`\{C_1,C_2\}`$ in $`RD`$, where $`C_1`$ (respectively, $`C_2`$) is the cluster of $`D`$ containing point $`k_1`$ (respectively, $`k_2`$). Note that $`RD`$ may have self-loops.

$``$ Stage S4 checks whether $`RD`$ is bipartite. If it is not, then S4 outputs “no” and stops. Otherwise, for each connected component $`K`$ of $`RD`$, the clusters in $`K`$ can be uniquely partitioned into two independent subsets $`V_{K,1}`$ and $`V_{K,2}`$ of clusters. If $`V_{K,1}`$ or $`V_{K,2}`$ contains both an $`L`$-cluster and an R-cluster, S4 outputs “no” and stops. Otherwise, $`V_{RD}`$ can be partitioned into two independent subsets $`V_{RD}^L`$ and $`V_{RD}^R`$ of clusters such that all $`L`$-clusters are in $`V_{RD}^L`$ and all R-clusters are in $`V_{RD}^R`$. Let $`V_D^L=\{k_p|k_p`$ is in a cluster in $`V_{RD}^L\}`$ and $`V_D^R=\{k_p|k_p`$ is in a cluster in $`V_{RD}^R\}`$.

$``$ Stage S5 embeds $`\mathrm{side}_p(B_k)`$ toward the left side of $`\mathrm{ske}(\chi )`$ for each $`k_pV_D^L`$.

###### Example 1

In Figure 9, $`\mathrm{pert}(\chi )`$ has 8 blocks $`B_1,\mathrm{},B_8`$. The left side of each $`B_k`$ is $`\mathrm{side}_1(B_k)`$. Also, $`\mathrm{fam}(\chi )=\{𝒞_1,\mathrm{},𝒞_6\}`$. An integer $`i`$ in a small square on $`\mathrm{side}_p(B_k)`$ for $`p=1`$ or 2 indicates that $`k_p`$ is on $`P_i`$. For example, the points on $`P_5`$ are $`5_1`$, $`6_1`$, and $`7_2`$. The letter $`L`$ is marked on $`\mathrm{side}_1(B_1)`$, indicating that $`\mathrm{side}_1(B_1)`$ must face left. The letter $`R`$ is marked on $`\mathrm{side}_1(B_7)`$, indicating that $`\mathrm{side}_1(B_7)`$ must face right. $`D`$ is shown in Figure 9(2). $`1_1`$ is an $`L`$-point while $`7_1`$ is an R-point. $`RD`$ is shown in Figure 9(3). $`C_1`$ is an $`L`$-cluster and $`C_7`$ is an R-cluster. $`RD`$ is bipartite and $`V_{RD}`$ can be partitioned into $`V_{RD}^L=\{C_1,C_4,C_9\}`$ and $`V_{RD}^R=\{C_2,C_3,C_5,C_6,C_7,C_8\}`$. Thus $`V_D^L=\{1_1,2_1,3_1,4_1,5_1,6_1,7_2,8_1\}`$ and $`V_D^R=\{1_2,2_2,3_2,4_2,5_2,6_2,7_1,8_2\}`$. Flipping $`B_7`$ in Figure 9(1) gives a satisfying embedding of $`\mathrm{pert}(\chi )`$. If $`8_2`$ were also on $`P_5`$, there would be an edge $`\{7_2,8_2\}`$ in $`D`$, which would cause $`C_9`$ and $`C_8`$ to be merged in $`RD`$ with a self-loop attached to it. In that case, $`RD`$ would not be bipartite and the CFE algorithm would output “no”.

#### 6.3.2 $`\mu `$ is an R-node

In this case, adding the edge $`(s,t)`$ to $`\mathrm{ske}(\mu )`$ yields a simple triconnected graph. Thus, the unique embedding of $`\mathrm{ske}(\mu )`$ with both $`s`$ and $`t`$ on the exterior face is $`\mathrm{ske}(\mu )`$ itself. Let $`\chi _1`$,…, $`\chi _b`$ be the children of $`\mu `$ in $`T`$. For each $`k\{1,\mathrm{},b\}`$, let $`B_{k,1}`$,…, $`B_{k,s_k}`$ be the minor blocks of $`\mathrm{pert}(\mu )`$ in $`\mathrm{pert}(\chi _k)`$. Note that $`s_k=1`$ when $`\chi _k`$ is an R-node or P-node. To process $`\mu `$, the CFE algorithm proceeds in five stages:

$``$ Stage R1 first computes $`𝒞_i^{}=\{\mathrm{img}(U_{i,j},\mu )|U_{i,j}𝒞_i\}`$ for every $`𝒞_i\mathrm{fam}(\mu )`$. Let $`^{}(\mu )`$ be the sequence of all $`𝒞_i^{}`$ with $`𝒞_i\mathrm{fam}(\mu )`$. Then R1 calls Theorem 3.8(2) to solve the CFE problem on input $`\mathrm{ske}(\mu )`$ and $`^{}(\mu )`$. If the output is “no”, R1 outputs “no” and stops. Otherwise, for each $`𝒞_i^{}`$ in $`^{}(\mu )`$, there is a face $`F_i`$ in $`\mathrm{ske}(\mu )`$ whose boundary intersects each $`\mathrm{img}(U_{i,j},\mu )𝒞_i^{}`$. Note that $`F_i`$ must be unique or else $`\mathrm{done}(𝒞_i)`$ would be a descendent of $`\mu `$, contradicting the fact $`𝒞_i\mathrm{fam}(\mu )`$.

$``$ Stage R2 computes the minor block $`B_{k,l}`$ of $`\mathrm{pert}(\mu )`$ strictly containing $`U_{i,j}`$ for each $`𝒞_i\mathrm{fam}(\mu )`$ and each type-4 $`U_{i,j}𝒞_i`$. If $`U_{i,j}`$ is two-sided for $`B_{k,l}`$, either side of $`B_{k,l}`$ may be embedded toward the face $`F_i`$; otherwise, for some $`p\{1,2\}`$, $`U_{i,j}`$ is side-$`p`$ for $`B_{k,l}`$ and it requires that $`\mathrm{side}_p(B_{k,l})`$ be embedded towards $`F_i`$.

$``$ Stage R3 makes sure that for every $`𝒞_i`$ straddling $`\mathrm{pert}(\mu )`$ and for every $`U_{i,j}𝒞_i`$ strictly contained in $`\mathrm{pert}(\mu )`$, a vertex in $`U_{i,j}`$ is embedded on the exterior face of $`\mathrm{pert}(\mu )`$. This is done by checking whether the following statements are all false.

1. There are an exterior edge $`e_k`$ of $`\mathrm{ske}(\mu )`$ and a minor block $`B_{k,l}`$ of $`\mathrm{pert}(\mu )`$ on $`e_k`$ with $`\mathrm{max}_{p\{1,2\}}\mathrm{ext}_p(B_{k,l})<0pt(\mu )`$; thus, both $`\mathrm{side}_1(B_{k,l})`$ and $`\mathrm{side}_2(B_{k,l})`$ must be embedded towards the exterior face of $`\mathrm{ske}(\mu )`$.
2. There are an interior edge $`e_k`$ of $`\mathrm{ske}(\mu )`$ and a minor block $`B_{k,l}`$ of $`\mathrm{pert}(\mu )`$ on $`e_k`$ with $`\mathrm{min}_{p\{0,1,2\}}\mathrm{ext}_p(B_{k,l})<0pt(\mu )`$; thus, at least one of $`\mathrm{side}_1(B_{k,l})`$ and $`\mathrm{side}_2(B_{k,l})`$ must be embedded towards the exterior face of $`\mathrm{ske}(\mu )`$.
3. There is a $`U_{i,j}\mathrm{sub}(\mu )`$ with $`0pt(\mathrm{done}(𝒞_i))<0pt(\mu )`$ (i.e., $`𝒞_i`$ straddles $`\mathrm{pert}(\mu )`$) and neither side of $`\mathrm{ske}(\mu )`$ contains an image in $`\mathrm{img}(U_{i,j},\mu )`$.
4. There are an S-child $`\chi _k`$ of $`\mu `$ and a $`U_{i,j}\mathrm{sub}(\chi _k)`$ such that $`0pt(\mathrm{done}(𝒞_i))<0pt(\mu )`$ and the virtual edge $`e_k`$ of $`\chi _k`$ is an interior edge in $`\mathrm{ske}(\mu )`$.

If at least one statement above holds, R3 outputs “no” and stops. Otherwise, for each minor block $`B_{k,l}`$ of $`\mathrm{pert}(\mu )`$ such that $`\mathrm{ext}_p(B_{k,l})<0pt(\mu )`$ for some $`p\{1,2\}`$, it requires that $`\mathrm{side}_p(B_{k,l})`$ be embedded towards the exterior face of $`\mathrm{ske}(\mu )`$. Note that since the above 2 is false, the representative $`e_k`$ of $`B_{k,l}`$ in $`\mathrm{ske}(\mu )`$ must be an exterior edge of $`\mathrm{ske}(\mu )`$.

$``$ Stage R4 first checks whether for some minor block $`B_{k,l}`$ of $`\mathrm{pert}(\mu )`$, the orientation requirements imposed on $`B_{k,l}`$ in Stage R2 or R3 are in conflict. If they are, R4 outputs “no” and stops. Otherwise, for each R-child or P-child $`\chi _k`$ of $`\mu `$, the minor block $`\mathrm{pert}(\chi _k)`$ can be oriented according to the requirements imposed on it, or arbitrarily if no requirement was imposed on it. Afterwards, for each S-child $`\chi _k`$ of $`\mu `$, it calls the S-procedure on input $`\chi _k`$ together with the orientation requirements that were imposed on the minor blocks in $`\mathrm{pert}(\chi _k)`$ in Stage R2 or R3. If the S-procedure on a $`\chi _k`$ outputs “no”, R4 outputs “no” and stops because $`\mathrm{pert}(\chi _k)`$ cannot be successfully embedded; otherwise, it has found a satisfying embedding of $`\mathrm{pert}(\mu )`$.

$``$ Stage R5 computes $`\mathrm{ext}_p(\mathrm{pert}(\mu ))`$ for $`p=0`$, 1, 2 as follows. Let $`\mathrm{xsub}^{}(\mu )=\{U_{i,j}\mathrm{xsub}(\mu )|`$ $`0pt(\mathrm{done}(𝒞_i))<0pt(\mu )\}`$; i.e., $`\mathrm{xsub}^{}(\mu )`$ consists of all $`U_{i,j}\mathrm{xsub}(\mu )`$ such that $`𝒞_i`$ straddles $`\mathrm{pert}(\mu )`$. Partition $`\mathrm{xsub}^{}(\mu )`$ into $`A_0`$, $`A_1`$, $`A_2`$ where $`A_0`$ (respectively, $`A_1`$ or $`A_2`$) consists of all $`U_{i,j}\mathrm{xsub}^{}(\mu )`$ such that $`U_{i,j}`$ is two-sided (respectively, side-1 or side-2) for $`\mathrm{pert}(\mu )`$. For $`i\{1,2\}`$, let $`\beta _i=\mathrm{min}_{p,B_{k,l}}\mathrm{ext}_p(B_{k,l})`$ where $`p`$ ranges over all integers in $`\{0,1,2\}`$ and $`B_{k,l}`$ ranges over all minor blocks on an edge of $`\mathrm{side}_i(\mathrm{ske}(\mu ))`$. Then, set

$`\mathrm{ext}_0(\mathrm{pert}(\mu ))`$ $`=`$ $`\underset{U_{i,j}A_0}{\mathrm{min}}0pt(\mathrm{done}(𝒞_i));`$
$`\mathrm{ext}_1(\mathrm{pert}(\mu ))`$ $`=`$ $`\mathrm{min}\{\beta _1,\underset{U_{i,j}A_1}{\mathrm{min}}0pt(\mathrm{done}(𝒞_i))\};`$
$`\mathrm{ext}_2(\mathrm{pert}(\mu ))`$ $`=`$ $`\mathrm{min}\{\beta _2,\underset{U_{i,j}A_2}{\mathrm{min}}0pt(\mathrm{done}(𝒞_i))\}.`$
This completes the processing of $`\mu `$.

###### Example 2

In Figure 10, the circles denote the vertices in $`\mathrm{ske}(\mu )`$, where $`s`$ and $`t`$ are the poles of $`\mathrm{pert}(\mu )`$. An integer $`i`$ in a small square at a side of a block $`B_{k,l}`$ indicates that a set in $`𝒞_i`$ has a vertex on that side of $`B_{k,l}`$. Also, $`\mathrm{fam}(\mu )=\{𝒞_1,𝒞_2\}`$. $`𝒞_1=\{U_{1,1},\mathrm{},U_{1,4}\}`$. $`U_{1,1}`$ is of type 3 and $`\mathrm{img}(U_{1,1},\mu )=\{e_3\}`$. $`U_{1,2}`$ and $`U_{1,3}`$ are of type 4, $`\mathrm{img}(U_{1,2},\mu )=\{e_2\}`$, and $`\mathrm{img}(U_{1,3},\mu )=\{e_4\}`$. $`U_{1,2}`$ is two-sided for $`B_{2,1}`$. $`U_{1,4}`$ is of type 2 and $`\mathrm{img}(U_{1,4},\mu )=\{d\}`$. $`𝒞_2`$ consists of $`U_{2,1}`$ and $`U_{2,2}`$, which are of type 4. $`\mathrm{img}(U_{2,1},\mu )=\{e_1\}`$ and $`\mathrm{img}(U_{2,2},\mu )=\{e_2\}`$. $`𝒞_3`$ is the only family straddling $`\mathrm{pert}(\mu )`$. $`U_{3,1}`$, $`U_{3,2}`$, and $`U_{3,3}`$ are the sets in $`𝒞_3`$ that intersect $`\mathrm{pert}(\mu )`$; the other sets in $`𝒞_3`$ are not shown in this figure. $`U_{3,1}`$ is of type 4 and $`\mathrm{img}(U_{3,1},\mu )=\{e_1\}`$. $`U_{3,2}`$ is of type 2 and is two-sided for $`\mathrm{pert}(\mu )`$; $`\mathrm{img}(U_{3,2},\mu )=\{a,b,c\}`$. Since $`U_{3,3}`$ is not strictly contained in $`\mathrm{pert}(\mu )`$, it is not tested during the processing of $`\mu `$. Note that $`\mathrm{pert}(\mu )`$ has a satisfying embedding as shown. For $`i=1,2`$, the boundary of $`F_i`$ intersects each set in $`𝒞_i`$. The exterior face of $`\mathrm{pert}(\mu )`$ contains an image of every set in $`𝒞_3`$ strictly contained in $`\mathrm{pert}(\mu )`$. The side of $`B_{4,1}`$ on which $`1`$ is marked must be embedded toward $`F_1`$. In contrast, whichever side of $`B_{2,1}`$ is embedded toward $`F_1`$, the boundary of $`F_1`$ intersects $`U_{1,2}`$. In the embedding of $`\mathrm{pert}(\mu )`$, $`𝒞_3`$ is side-1 (respectively, side-0) exterior-forcing for $`\mathrm{pert}(\mu )`$ because of $`U_{3,1}`$ (respectively, $`U_{3,2}`$).

#### 6.3.3 $`\mu `$ is a P-node

In this case, $`\mathrm{ske}(\mu )`$ consists of parallel edges $`e_1,e_2,\mathrm{},e_b`$ between its two poles with $`b2`$. Let $`\chi _1`$,…, $`\chi _b`$ be the children of $`\mu `$ in $`T`$. For each $`k\{1,\mathrm{},b\}`$, let $`B_{k,1}`$,…, $`B_{k,s_k}`$ be the minor blocks of $`\mathrm{pert}(\mu )`$ in $`\mathrm{pert}(\chi _k)`$. When embedding $`\mathrm{ske}(\mu )`$, edges $`e_1`$ through $`e_b`$ can be embedded in any order. The CFE algorithm first finds a proper embedding of $`\mathrm{ske}(\mu )`$ in three stages:

$``$ Stage P1 constructs an auxiliary graph $`H=(V_H,E_H)`$ with $`V_H=\{e_1,\mathrm{},e_b\}`$ by performing the following steps in turn for every $`𝒞_i\mathrm{fam}(\mu )`$:

1. Compute $`S_i=_{U_{i,j}}\mathrm{img}(U_{i,j},\mu )`$, where $`U_{i,j}`$ ranges over all type-3 or type-4 sets in $`𝒞_i`$. Let $`m_i`$ be the number of edges in $`S_i`$. Then, $`m_i2`$; otherwise $`𝒞_i`$ would be in $`\mathrm{fam}(\chi _k)`$ for some $`k\{1,\mathrm{},b\}`$.
2. If $`m_i3`$, then output “no” and stop since $`\mathrm{pert}(\mu )`$ does not satisfy $`𝒞_i`$.
3. Insert edge $`\{e_k,e_k^{}\}`$ to $`H`$, where $`e_k`$ and $`e_k^{}`$ are the two edges in $`S_i`$.

Note that for each $`𝒞_i\mathrm{fam}(\mu )`$, no set in $`𝒞_i`$ is of type 2, and each type-1 set in $`𝒞_i`$ contains a pole of $`\mathrm{pert}(\mu )`$, which is on every face of all embeddings of $`\mathrm{ske}(\mu )`$. For this reason, neither type-1 nor type-2 set in $`𝒞_i`$ is considered in the construction of $`H`$.

$``$ Stage P2 checks whether both statements below are false in order to ensure that for every $`𝒞_i`$ straddling $`\mathrm{pert}(\mu )`$ and every $`U_{i,j}𝒞_i`$ strictly contained in $`\mathrm{pert}(\mu )`$, a vertex in $`U_{i,j}`$ is embedded on the exterior face of $`\mathrm{pert}(\mu )`$.

1. There is a minor block $`B_{k,l}`$ of $`\mathrm{pert}(\mu )`$ with $`\mathrm{max}_{p\{1,2\}}\mathrm{ext}_p(B_{k,l})<0pt(\mu )`$.
2. There are at least three edges $`e_k`$ in $`\mathrm{ske}(\mu )`$ such that (1) there is a minor block $`B_{k,l}`$ on $`e_k`$ with $`\mathrm{min}_{p\{0,1,2\}}\mathrm{ext}_p(B_{k,l})<0pt(\mu )`$; or (2) $`\chi _k`$ is an S-node and there exists $`U_{i,j}`$ in $`\mathrm{sub}(\chi _k)`$ with $`0pt(\mathrm{done}(𝒞_i))<0pt(\mu )`$.

If Statement 1 or 2 holds, P2 outputs “no” and stops. Otherwise, it marks each $`e_kV_H`$ for which Statement 2(a) or 2(b) holds. Note that at most two $`e_kV_H`$ are marked, and each marked $`e_kV_H`$ must be an exterior edge in any satisfying embedding of $`\mathrm{ske}(\mu )`$.

$``$ Stage P3 outputs “no” and stops if an $`e_kV_H`$ has degree at least three in $`H`$ or a marked $`e_kV_H`$ has degree 2 in $`H`$. Otherwise, P3 finds and fixes an embedding of $`\mathrm{ske}(\mu )`$ where (1) each marked $`e_kV_H`$ is in the exterior face and (2) for every $`\{e_k,e_k^{}\}E_H`$, $`e_k`$ and $`e_k^{}`$ form the boundary of a face. For each $`𝒞_i\mathrm{fam}(\mu )`$, let $`F_i`$ be the face in the fixed embedding of $`\mathrm{ske}(\mu )`$ whose boundary is formed by the two edges in $`S_i`$. Note that for each $`U_{i,j}𝒞_i`$, the boundary of $`F_i`$ intersects $`\mathrm{img}(U_{i,j},\mu )`$.

Next, the CFE algorithm tries to embed $`\mathrm{pert}(\mu )`$ based on the embedding of $`\mathrm{ske}(\mu )`$ fixed in Stage P3 through the same stages as Stages R2 through R5 in §6.3.2 except that in the stage corresponding to R5, $`A_0=\mathrm{}`$ and the algorithm sets $`\mathrm{ext}_0(\mathrm{pert}(\mu ))=\mathrm{}`$. This completes the processing of $`\mu `$.

###### Example 3

In Figure 11, $`\mathrm{fam}(\mu )=\{𝒞_1,𝒞_2\}`$. $`𝒞_1=\{U_{1,1},U_{1,2},U_{1,3}\}`$. Both $`U_{1,1}`$ and $`U_{1,2}`$ are of type 4; $`\mathrm{img}(U_{1,1},\mu )=\{e_1\}`$ and $`\mathrm{img}(U_{1,2},\mu )=\{e_2\}`$. $`U_{1,3}`$ is of type 1 and needs not be tested during the processing of $`\mu `$. $`𝒞_2=\{U_{2,1},U_{2,2}\}`$. $`U_{2,1}`$ is of type 3 and $`\mathrm{img}(U_{2,1},\mu )=\{e_3\}`$. $`U_{2,2}`$ is of type 4 and $`\mathrm{img}(U_{2,2},\mu )=\{e_4\}`$. $`𝒞_3`$ is the only family straddling $`\mathrm{pert}(\mu )`$. $`\{U_{3,1}`$ and $`U_{3,2}\}`$ are the sets in $`𝒞_3`$ that intersect $`\mathrm{pert}(\mu )`$; the other sets in $`𝒞_3`$ are not shown in this figure. Since $`U_{3,2}`$ contains the pole $`t`$ of $`\mathrm{pert}(\mu )`$, it is not tested during the processing of $`\mu `$. $`U_{3,1}`$ is of type 4 and $`\mathrm{img}(U_{3,1},\mu )=\{e_1\}`$. $`V_H=\{e_1,e_2,e_3,e_4\}`$ and $`E_H=\{\{e_1,e_2\},\{e_3,e_4\}\}`$. Only $`e_1`$ is marked in graph $`H`$. Figure 11(2) shows an embedding of $`\mathrm{ske}(\mu )`$ that might be found and fixed in Stage P3. This embedding of $`\mathrm{ske}(\mu )`$ results in a satisfying embedding of $`\mathrm{pert}(\mu )`$ as shown. If either $`𝒞_1`$ had another set strictly contained in block $`B_{4,1}`$ or $`𝒞_3`$ had another set strictly contained in $`B_{2,1}`$, then $`\mathrm{pert}(\mu )`$ has no satisfying embedding.

This completes the description of the CFE algorithm. Its correctness follows from the above discussion and Fact 6.3.

### 6.4 Implementation and analysis

We implement the CFE algorithm as follows. The nodes of $`T`$ are identified by their pre-order numbers. At each node $`\mu T`$, we store $`0pt(\mu )`$ and the pre-order number of the largest node in $`T_\mu `$. Let $`\chi _1,\mathrm{},\chi _b`$ be the children of $`\mu `$. The nodes in $`T_{\chi _1},\mathrm{},T_{\chi _b}`$ form an ordered partition of the nodes in $`T_\mu \{\mu \}`$. For a node $`\nu `$, we can check whether $`\nu `$ is in $`T_\mu `$ in $`O(1)`$ time. If $`\nu T_\mu `$, we can find the subtree $`T_{\chi _k}`$ containing $`\nu `$ in $`O(\mathrm{log}|𝒢|)`$ time, by binary searching the children of $`\mu `$. We equip $`T`$ with a data structure which can be constructed in linear time and outputs a least common ancestor query in $`O(1)`$ time .

We also store $`\mathrm{ske}(\mu )`$ at $`\mu `$. Each $`\mu `$ has a pointer to its virtual edge in its parent’s skeleton. For each non-pole vertex of $`\mathrm{ske}(\mu )`$, we mark $`\mu `$ as its proper allocation node. This takes $`O(|𝒢|)`$ total time by Fact 6.2(1). Each edge $`e`$ of $`𝒢`$ has a pointer to the leaf node in $`T`$ that represents $`e`$.

###### Lemma 6.4

Given $`𝒢`$, $``$, and $`T`$, we can compute $`\mathrm{fam}(\mu )`$, $`\mathrm{sub}(\mu )`$, $`\mathrm{done}(𝒞_i)`$, and $`\mathrm{done}(U_{i,j})`$ for all nodes $`\mu `$ of $`T`$, all $`𝒞_i`$ in $``$, and all $`U_{i,j}`$ in $`𝒞_i`$ in $`O(I)`$ total time.

Proof.  For each vertex $`v`$ of $`𝒢`$, let $`\mathrm{low}(v)`$ be the deepest allocation node of $`v`$ in $`T`$. In $`O(|𝒢|)`$ time, we can compute $`\mathrm{low}(v)`$ for all vertices $`v`$ of $`𝒢`$. For a set $`U_{i,j}𝒞_i`$, if a pole of $`𝒢`$ is in $`U_{i,j}`$, then $`\mathrm{done}(U_{i,j})`$ is the root of $`T`$; otherwise, $`\mathrm{done}(U_{i,j})`$ is the least common ancestor of all $`\mathrm{low}(v)`$ with $`vU_{i,j}`$. So, $`\mathrm{done}(U_{i,j})`$ can be computed in $`O(|U_{i,j}|)`$ time. Let $`\mathrm{low}(U_{i,j})`$ be the deepest one among all $`\mathrm{low}(v)`$ with $`vU_{i,j}`$. We can compute $`\mathrm{low}(U_{i,j})`$ in $`O(|U_{i,j}|)`$ time. Since $`\mathrm{done}(𝒞_i)`$ is the least common ancestor of all $`\mathrm{low}(U_{i,j})`$ with $`U_{i,j}𝒞_i`$, it can be computed in $`O(|𝒞_i|)`$ time. Thus, in $`O(I)`$ total time, we can compute $`\mathrm{done}(U_{i,j})`$ and $`\mathrm{done}(𝒞_i)`$ for all $`𝒞_i`$ in $``$ and all $`U_{i,j}`$ in $`𝒞_i`$. Afterwards, in $`O(I)`$ total time, we can compute $`\mathrm{fam}(\mu )`$ and $`\mathrm{sub}(\mu )`$ for all nodes $`\mu `$ of $`T`$.

After processing $`\mu `$, the CFE algorithm records the following information:

1. the embedding of $`\mathrm{ske}(\mu )`$;
2. $`\mathrm{ext}_p(\mathrm{pert}(\mu ))`$ for $`p=0`$, 1, and 2;
3. the edges and vertices on $`\mathrm{side}_1(\mathrm{ske}(\mu ))`$ and $`\mathrm{side}_2(\mathrm{ske}(\mu ))`$, respectively;
4. an integer $`p=0`$, 1 or 2, for each $`U_{i,j}\mathrm{xsub}(\mu )`$, indicating whether $`U_{i,j}`$ is two-sided, side-1, or side-2 for $`\mathrm{pert}(\mu )`$, respectively.

The CFE algorithm processes a P-node or R-node $`\mu `$ with the five operations below.

Operation 1 uses $`O(|U_{i,j}|+\mathrm{log}|𝒢|)`$ time to determine the type of a given $`U_{i,j}`$ in $`\mathrm{xfam}(\mu )`$ and finds $`\mathrm{img}(U_{i,j},\mu )`$ as follows. Let $`\nu =\mathrm{done}(U_{i,j})`$.

Case 1: $`0pt(\nu )0pt(\mu )`$. Then, $`U_{i,j}`$ is of type 1 or 2 for $`\mathrm{pert}(\mu )`$. $`U_{i,j}`$ is of type 1 if and only if it contains a pole of $`\mathrm{pert}(\mu )`$. Also, $`\mathrm{img}(U_{i,j},\mu )`$ consists of all $`vU_{i,j}`$ which are also in $`\mathrm{ske}(\mu )`$. Note that $`v\mathrm{ske}(\mu )`$ if and only if $`\mu `$ is the proper allocation node of $`v`$ or $`v`$ is a pole of $`\mathrm{pert}(\mu )`$.

Case 2: $`0pt(\nu )=0pt(\mu )+1`$ and $`\nu `$ is an S-node. Then, $`U_{i,j}`$ is of type 3 for $`\mathrm{pert}(\mu )`$. Also, $`\mathrm{img}(U_{i,j},\mu )`$ consists of the virtual edge of $`\nu `$ in $`\mathrm{ske}(\mu )`$.

Case 3: otherwise. Then, $`U_{i,j}`$ is of type-4 for $`\mathrm{pert}(\mu )`$. Also, $`\mathrm{img}(U_{i,j},\mu )`$ is the virtual edge of $`\chi _k`$ in $`\mathrm{ske}(\mu )`$, where $`\chi _k`$ is the child of $`\mu `$ such that $`\nu `$ is in the subtree $`T_{\chi _k}`$.

Operation 2 checks in $`O(|U_{i,j}|)`$ time whether a given $`U_{i,j}\mathrm{xsub}(\mu )`$ has a vertex on either side of $`\mathrm{pert}(\mu )`$ after an embedding of $`\mathrm{pert}(\mu )`$ is fixed. If $`U_{i,j}\mathrm{sub}(\mu )`$, we check whether a vertex in $`\mathrm{img}(U_{i,j},\mu )`$ is on either side of $`\mathrm{ske}(\mu )`$. If $`U_{i,j}\mathrm{sub}(\chi _k)`$ for an S-child $`\chi _k`$ of $`\mu `$, we check whether the virtual edge $`e_k`$ of $`\chi _k`$ is on either side of $`\mathrm{ske}(\mu )`$.

Operation 3 uses $`O(1)`$ time to check whether a given $`U_{i,j}\mathrm{xsub}(\mu )`$ is in $`\mathrm{xsub}^{}(\mu )`$ by checking whether $`0pt(\mathrm{done}(𝒞_i))<0pt(\mu )`$.

Operation 4 checks whether a given $`U_{i,j}`$ is strictly contained in $`\mathrm{pert}(\mu )`$ and if so, further computes the minor block $`B`$ of $`\mathrm{pert}(\mu )`$ strictly containing $`U_{i,j}`$ in $`O(|U_{i,j}|+\mathrm{log}|𝒢|)`$ total time. For the first task, we check whether (1) $`\nu =\mathrm{done}(U_{i,j})`$ is a descendent of $`\mu `$, or (2) $`\nu =\mu `$ and $`U_{i,j}`$ contains no pole of $`\mathrm{pert}(\mu )`$. For the second task, we first find the child $`\chi _k`$ of $`\mu `$ such that $`T_{\chi _k}`$ contains $`\nu `$. If $`\chi _k`$ is not an S-node, $`\mathrm{pert}(\chi _k)`$ is $`B`$; otherwise, $`B`$ is $`\mathrm{pert}(\eta )`$ where $`\eta `$ is the child of $`\chi _k`$ such that $`T_\eta `$ contains $`\nu `$.

Operation 5 checks in $`O(\mathrm{log}|𝒢|)`$ time whether a given type-4 $`U_{i,j}`$ for $`\mathrm{pert}(\mu )`$ is side-1, side-2, or two-sided for the minor block $`B_{k,l}`$ in $`\mathrm{pert}(\mu )`$ strictly containing $`U_{i,j}`$. Let $`\eta =\mathrm{node}(B_{k,l})`$ and $`\nu =\mathrm{done}(U_{i,j})`$. Note that $`\eta `$ has been processed. If $`\eta =\nu `$, this operation takes $`O(1)`$ time using the information stored for $`\eta `$. If $`\nu `$ is a descendent of $`\eta `$, the representative $`e`$ of $`\nu `$ in $`\mathrm{ske}(\eta )`$ can be found in $`O(\mathrm{log}|𝒢|)`$ time. Then, it takes $`O(\mathrm{log}|𝒢|)`$ time to check whether $`e`$ is on $`\mathrm{side}_1(\mathrm{ske}(\eta ))`$ or $`\mathrm{side}_2(\mathrm{ske}(\eta ))`$ using the information stored for $`\eta `$.

###### Lemma 6.5

1. $`\{\mathrm{xfam}(\mu )|\mu `$ is a P-node or R-node} is a partition of $`\{𝒞_1,\mathrm{},𝒞_q\}`$.
2. $`\{\mathrm{xsub}(\mu )|\mu `$ is a P-node or R-node} is a partition of $`𝒞_1\mathrm{}𝒞_q`$.
3. Each input family $`𝒞_i`$ is processed exactly once.
4. Each input $`U_{i,j}`$ is processed at most twice, and the total time spent on processing $`U_{i,j}`$ is $`O(|U_{i,j}|+\mathrm{log}|𝒢|)`$.

Proof.  Statements 1 and 2 are straightforward. Statement 3 holds since each $`𝒞_i`$ is processed only when the node $`\mu `$ with $`𝒞_i\mathrm{xfam}(\mu )`$ is processed. Each $`U_{i,j}`$ is processed once when the node $`\mu `$ with $`U_{i,j}\mathrm{xsub}(\mu )`$ is processed and once when the node $`\varphi `$ with $`𝒞_i\mathrm{xfam}(\varphi )`$ is processed. When $`U_{i,j}`$ is processed, we perform some of Operations 1 through 5 on it. Since an operation takes $`O(|U_{i,j}|+\mathrm{log}|𝒢|)`$ time, Statement 4 holds.

We now bound the time of processing an R-node or P-node $`\mu `$. Let $`\mathrm{xske}(\mu )`$ be obtained from $`\mathrm{ske}(\mu )`$ by replacing the virtual edge of each S-child $`\chi _k`$ of $`\mu `$ with $`\mathrm{ske}(\chi _k)`$. Let $`n_\mu `$ be the number of vertices in $`\mathrm{xske}(\mu )`$. Let $`N_\mu =_{𝒞_i\mathrm{xfam}(\mu )}|𝒞_i|`$. Recall that $`\mu `$ is processed using some of the following operations:

1. Process the sets $`U_{i,j}`$ in the families $`𝒞_i\mathrm{xfam}(\mu )`$.
2. Call Theorem 3.8(2) on input $`\mathrm{ske}(\mu )`$ and $`^{}(\mu )`$.
3. Call the S-procedure on $`\chi _k`$ for the S-children $`\chi _k`$ of $`\mu `$.
4. Compute $`\mathrm{ext}_p(\mathrm{pert}(\mu ))`$ for $`p=0`$, 1, and 2.
5. Construct auxiliary graphs $`D`$, $`RD`$ and $`H`$, and operate on them.

Note that each $`K\{D,RD,H\}`$ is constructed and operated on in $`O(|K|)`$ total time. Since $`_K|K|n_\mu `$ where $`K`$ ranges over all auxiliary graphs constructed during the processing of $`\mu `$, it takes $`O(n_\mu )`$ total time to process the auxiliary graphs for $`\mu `$. Therefore, the above operations take $`O((n_\mu +N_\mu )\mathrm{log}I)`$ time in total. By summing over all P-nodes and R-nodes $`\mu `$ of $`T`$, and by Theorem 3.8, Fact 6.2(1), and Lemma 6.5, the CFE algorithm runs in the desired total time, completing the proof of Theorem 6.1.

## 7 Directions for further research

We have proved that the CFE problem can be solved in $`O(I\mathrm{log}I)`$ time for the special case where for each input family $`𝒞_i`$, each set in $`𝒞_i`$ induces a connected subgraph of the input graph $`𝒢`$. One direction for further research would be to reduce the running time to linear. Such a result might lead to substantial simplification of the SPQR decomposition or an entirely different data structure. Another worthy direction would be to solve more general cases in similar time bounds. Beyond these technical open problems, it would be of significance to find further applications of the CFE problem than VLSI layout and topological inference as well as to identify novel and fundamental constrained planar embeddings.

## Acknowledgments

We wish to thank the anonymous referee for many helpful suggestions.