数理解析研究所講究録1093 巻 1999 年 33-38

33

Common-face embeddings of planar graphs with applications*

石瀬中 (Zhi-Zhong Chen), Xin He, Ming-Yang Kao
Tokyo Denki University, SUNY at Buffalo, Yale University

1

Introduction

Theorem 2. 1 The $CFE$ problem is NP-complete.

It is a fundamental problem in mathematics to embed a graph into a given space whilecertain objectives required by applications. A graphis called planar if it can be embedded on the planeso that any pair of edges can only intersect at theirendpoints; 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.
In this paper, we initiate the study into the following new planarity problem. Let be a planargraph. Assume that is simple. Let
be a se$\mathrm{o}\mathrm{p}\mathrm{t}\mathrm{i}_{\mathrm{I}\mathrm{n}}\mathrm{i}_{\mathrm{Z}}\mathrm{i}\mathrm{n}\mathrm{g}$$\mathcal{G}$$\mathcal{M}$$\mathcal{G}$quence, where each is a family of vertex subsets of . A plane embedding offies if boundary of some face in intersects
every set in .
satisfies if it satisfies all .
ifhas
an embedding that satisfies
satisfies. The CFE problem is the following:
Input: and.
Question: Does?
We show that the CFE problem is NP-complete.
For the special case where every vertex subset in
induces a connectedof , we givean-time algorithm, where is the input size. The CFE problem arises naturally fromtopological inference [1]. For instance, a less general and efficient version of our algorithm for the
special case has been employed to design fast algorithms for reconstructing maps ffom scrambled
partial data in geometric information systems. In
this application, each vertex subset indescribes
a recognizable geographical feature, and each family in
is a set of features that are known to benear each other. Similarly, our algorithm for the
special case can compute a constrainted layout of
VLSI modules, where each vertex subset consistsof the ports of a module, and each subset family
specifies a set of modules that are required to beclose to each other.
$C_{1},$$\ldots,C_{q}$$C_{i}$$\Phi$$\mathcal{G}$$\mathcal{G}sat\dot{i}S-$$\dot{\mathrm{t}}\mathrm{h}\mathrm{e}$$C_{i}$$\Phi$$C_{i}$$\mathcal{G}$.

$\mathcal{M}$$\Phi$$\mathcal{M}$$C_{i}$$\mathcal{G}$$\mathcal{M}$$\mathcal{G}$$\bullet$$\lambda 4$$\mathcal{G}\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}6^{\Gamma}\mathcal{M}$The size
of is the total cardinality of thesets in . The
of At is $|C_{1}|+\cdots+|C_{q}|$ . $|G|$denotes the total number of vertices and edges ina graph . Let. The next theorem
is the main theorem of this paper.
$|C_{i}|$$C_{i}$$C_{i}$$S\dot{i}ze|\mathcal{M}|$$G$$\alpha=|\mathcal{G}|+|\mathcal{M}|$

Theorem 2. 2 If every vertex subset induces a connected subgraph of , then the $CFE$
problem can be solved intime.
$\mathcal{M}\dot{i}n-$$\mathcal{G}$$O(\alpha\log\sigma)$

Proof: We consider three special cases:
Case Ml: is connected.
Case M2: is biconnected.
Case M3: is triconnected.
Theorem 3. 8 solves Case M3. Theorem 4. 1 reduces this theorem to Case Ml. \S 5 reduces Case
Ml to M2. Theorem 6. 1 uses Theorem 3. 8
solve Case M2.
The remainder of the paper assumes that every
vertex subset of in A4 induces a connected sub$\mathcal{G}$$\mathcal{G}$$\mathcal{G}$$\square \mathrm{t}\mathrm{o}$$\mathcal{G}$graph of .
$\mathcal{G}$3

Case M3$\mathcal{M}$$\mathrm{s}\mathrm{u}\mathrm{b}\mathrm{g}\mathrm{r}\mathrm{a}_{\mathrm{P}}\mathrm{h}$$O(\alpha\log\alpha)$$\mathcal{G}$$\alpha$$\lambda 4$$\Lambda\Lambda$

This section assumes that is triconnected. Then,
has a unique combinatorial embedding up to theof the exterior face. Thus, the CFE problem reduces in linear time to that of finding all thefaces in the embedding whose boundaries intersect
every set in some . The naive algorithm takes
time. We solve the latter problem more
efficiently by recursively solving the ACF problem
defined below.
Throughout this section, for technical convenience, the vertices of a plane graph are indexed by
distinct positive integers. The faces are indexed bypositive integers or-l. The faces indexed by positive integers have distinct indices and are called
the positive faces. Those indexed by $-1$ are thenegative faces.
Letbe a plane graph. A $vf$-set of is a setof vertices and positive faces in . A
isa family of -sets; a $vf$-sequence is a sequence of-families. Let $N$ be a -sequenceof. Also, let $D=\{S_{1}, \ldots, S_{d}\}$ be a -family of .
$\mathcal{G}$$\mathcal{G}$$\mathrm{d}_{\mathrm{l}\mathrm{O}}\mathrm{i}_{\mathrm{C}\mathrm{e}}$$C_{i}$$\Theta(|\mathcal{G}||\mathcal{M}|)$$\mathcal{H}$2

The main results$vf- fam\dot{i}ly$$\mathrm{v}\mathrm{f}$$\mathrm{v}\mathrm{f}$*A preliminary version was presented at$\mathcal{H}$$\mathcal{H}$.

$\mathrm{S}\mathrm{O}\mathrm{D}\mathrm{A}’ 99$$\mathcal{H}$$\mathrm{v}\mathrm{f}$$D_{1},$$\mathrm{v}\mathrm{f}$$\ldots,D_{q}$$\mathcal{H}$

34

.
.
..

be the set
be the set of faces in . LetLetof vertices in .
$|D|=|S_{1}|+\cdots+|S_{d}|$ ; similarly, $|N|=|D_{1}|+$$U_{i}$$S_{i}$$F_{t}$$S_{i}$$...+|D_{q}|$.

is the set of vertices in the intersection-sets in $D$ .
is the set of positive faces $F$ of such
$F$ is a face inor its boundarythat for each.
intersects$\mathrm{v}\mathrm{f}$$\mathcal{H}$$\Lambda_{\mathrm{f}}(\mathcal{H}, D)$$S_{i}$$S_{i},$$S_{i}-\Lambda_{\mathrm{v}}(D)$$\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H},D)=\Lambda_{\mathrm{V}}(D)\cup\Lambda \mathrm{f}(\mathcal{H},D)$$\bullet$$\mathcal{H}$$U$$\mathcal{H}’$$\Lambda_{\mathrm{v}}(D)$$\bullet$of thepositive faces in whose boundaries each containat least two distinct vertices in . Let $V’$ and $E’$
be the sets of boundary vertices and edges of thebe the planefaces in $F\cup F_{U}$ , respectively. Let$E’$ .
$V’\cupU$
andsubgraph of consisting of$U’$
be the set of vertices which are of degreeLet; note that each vertex in $U’$at least three inappears on the boundaries of at least two faces in. A critical path $P$ in is a maximal pathsuch that (1) every internal vertex of $P$ appears
only once in it, and (2) no internal vertex of $P$ is in$U\cup U’$ . By the choice of $U’$ , every intemal vertex
of a critical path is of degree 2 in . We use thisbe the. Let
property to further simplify
eachreplacingbyplane graph obtained fromendpoints.
its
critical parh with an edge between
This edge is embedded by the same curve in theplane as the path is. For technical consistency, if acritical path forms a cycle and its endpoint is not
in $U\cup U’$ , then we replace it with a self-loop forthe vertex of the cycle with the smallest index.
is given the same index as in
Each vertex in. The closure of the interior of each face ofis the union of those of several faces or just one in
and $F’$ be one in . Let. Let $F$ be a face in(resp., ) denote the closure of the interior of $F$, then $F$ and $F’$ are regarded(resp., $F’$ ). If
as the same face, and $F$ is assigned the same index
as $F$’ is in . For technical conciseness,inthese two faces are identified with each other. If
is the union of the closures of the interiors of two$F$ is not the same as any faceor more faces inin and is indexed by-l.

.

The ACF problem is the following:
and $N$ .
Input:.
Output:need
To solve the ACF problem recursively,
not be simple or triconnected. Furthermore, thosefaces that are indexed by $-1$ are ruled out as final output during recursions. To solve the problem
is meant as a sucefficiently, each vertex incinct representation of all the faces whose boundaries contain that vertex. Similarly, the positive
and the output are reprefaces in the input
sented by their indices.
The next lemma relates the CFE problem andthe ACF problem.
$\mathcal{H}$$\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H},D1),$$\ldots,\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H}_{1}D)q$$\mathcal{H}$$\Lambda_{\mathrm{v}}(D_{i})$$D_{i}$$\mathcal{H}$$\mathcal{H}’$$\mathcal{H}’$$F\cup \mathcal{F}_{U}$$\mathcal{H}’$$\mathcal{H}’$$\mathcal{H}\phi S$$\mathcal{H}\phi S$$\mathcal{H}$$of\mathcal{G}$$t\dot{i}ve‘ t$$\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{G},Ci)\neq\emptyset$$C_{i},$$\sigma’$$\sigma$$\sigma=\sigma’$$\mathcal{H}$$\mathcal{H}\theta S$

A counting lemma

3.1$\sigma$Lemma 3. 2 1. Let and bebeandin . Let
faces in . Then,andboth and are on the $boundar\dot{i}es$ of both
both
edge
boundary
a
and
of
form
iff
and .
2. Given a setof vertices in , there are$O(|U|)$ faces
whose boundaries each containin .
at least two, theoe are $O(|\tau|)$
3. Given a set of faces
are each on the boundaries ofvertices inat least two faces in $F$ .
$v_{2}$$v_{1}$$\mathcal{G}$$F_{1}$$v_{2}$$v_{1}$$\mathcal{H},$$\mathcal{H}$$F_{1}$$v_{2}$$v_{1}$$F_{2}$$d\dot{i}st\dot{i}nctveri\dot{i}Ces$$d_{\dot{i}}stinct$$F_{2}$$F_{1}$$\mathcal{G}$$\mathcal{H}$$\mathcal{H}\phi S$$\mathcal{H}$be indexed by posiLemma 3. 1 Let the faces
integers. Then, the output to the $CFE$ problem.
is yes” iff for all$\mathcal{H}\phi S$$\mathcal{H}’$

1. Given and , we can computein $O(|\mathcal{H}|+|S|)$ time.
, then. If
2. Let $S’$ be a $vf$-set ofLemma 3. 4

$F_{2}$$U$$\mathcal{G}$$U$$\dot{i}n\mathcal{G}$$\mathcal{F}$$S’\subseteq S$$\mathcal{H}\phi S$$\dot{i}n\mathcal{G}$$vert_{\dot{i}C}es$$S$$\mathcal{H}$$\mathcal{H}\phi S$$\mathcal{H}\phi S’=(\mathcal{H}\psi s)\theta s’$.

3. If simplifies over a $vf$-set
then $|\mathcal{H}\phi S|=O(|S|)$ .
$\mathcal{H}$$\mathcal{G}$$S^{*}w\dot{i}thS\subseteq S^{*}$,$\mathcal{G}wh_{\dot{i}}ch$

is simple and $tr\dot{i}conneCted$,
Corollary 3. 3 Ifthen the output of the $ACF$ problem has size$\mathcal{H}$$O(|N|)$.

Algorithms for ACF

3.3

To solve the ACF problem recursively, we use simplification to reduce the number of and the number of sets in each .
; simFor brevity, let. Given a vf-set
ilarly,wefor allof , we say $D\leq S^{*}$ if
for all .
say $N\leq S^{*}$ if
Lemmas 3. 5 and 3. 6 below reduce to 1 thein $N$ in the ACF problem.
number of$D_{i}$$D_{i}$

A simplification technique
To solve the ACF problem efficiently, we simplify
3.2

the input graph by removing unnecessary edges andvertices as follows.
of , the topological subgraphFor a -setof constructed as follows is said to$S$$\mathrm{v}\mathrm{f}$$\mathcal{H}\theta S$$\mathcal{H}$$\mathcal{H}$over .
$S$$S_{i;}$$S_{i}\subseteq S^{*}$$\mathcal{H}$$D_{i}\leq S^{*}$$D_{i}$$D_{i}$

Let2.
Lemma 3. 5 Assume,. Let $N_{r}=D_{\lceil q/2}1+1,$ ,
.
and
$q$

Let and be the sets of vertices and positivebe the set of thefaces in , respectively. Let$\mathcal{F}$$S$$S^{*}$$S\dot{i}mplih$$\mathcal{H}$$U$$\mathcal{H}\phi D=\mathcal{H}\phi(S_{1}\cup\cdots\cup S_{d})$$\mathcal{H}\phi N=\mathcal{H}\phi(D_{1}\cup\cdots\cup D_{q})$$\mathcal{F}_{U}$$D_{1},$$\ldots$$\geq$$\ldots$$D_{\lceil q/2\rceil}$$\mathcal{H}_{\ell}=\mathcal{H}\theta N_{l}$$\mathcal{H}_{r}=\mathcal{H}\theta Nr$$N_{l}$$D_{q}$

$=$

. Let

35

1.
and $N$, we can computeandin $O(|\mathcal{H}|+|N|)$ total time.
. Simi2. For
larly, for $\lceil q/2\rceil+1\leq i\leq q,$.
S. If simplifies over a $vf$-set
with $N\leq$, then$G_{\dot{i}}ven\mathcal{H}$$\mathcal{H}_{r}$$\mathcal{H}_{\ell}$$1\leq i\leq\lceil q/2\rceil,$$\mathcal{H}\theta D_{\dot{\iota}}=\mathcal{H}_{\ell}\theta Di$$\mathcal{H}\theta D_{i}=\mathcal{H}_{r}\phi D_{i}$$\mathcal{H}$$S^{*}$$S^{*}$$\mathcal{G}$$|\mathcal{H}_{\ell}|=O(|D_{1}|+\cdots+|D_{\lceil q/2\rceil}|)and|\mathcal{H}_{r}|=$$O(|D_{\lceil q/\rceil}2+1|+\cdots+|D_{q}|)$.

labeled . For every , let
be the family consisting of all sets such that some edge ofislabeledwith $U\in C_{h}$ . For each , let
be thesequence consisting of the -local families inaswell as the familyis{-local}for each.
with$C_{h}$$B_{j}$$\mathcal{U}_{j}$$U$$B_{j}$$C_{h}$$\mathcal{M}_{i}$$\mathcal{G}_{i}$$\mathcal{M}$$\mathcal{G}_{i}$$U\in \mathcal{U}_{j}|U$$\mathcal{U}_{j,i}=$$\mathcal{G}_{i}$$\mathcal{G}_{i}\in V(B_{j})$$B_{j}$

Theorem 4. 1
satisfies $M$ iff every. Consequently, Theorem 2. 2 holds$\mathcal{G}$Lemma 3. 6 Assume
. Let
.
1.
.
2. If simplifies over a $vf$-set $S^{*}w\dot{i}thN\leq$, then.
3. If simplifies over a $vf$-set
with $N\leq$$N$, then given and , we can compute allin$O(|\mathcal{H}|+|N|\log(q+1))$ total time.
$q\geq 1$$\mathcal{H}_{i}=\mathcal{H}\phi D_{i}$$\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H},D_{i})=\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H}_{i}, D_{i})$$\mathcal{H}$$S^{*}$$\mathcal{H}$$S^{*}$$\mathcal{G}$$S^{*}$$\mathcal{H}$$\mathcal{H}_{i}$Lemma 3. 7 Let$\{S_{\lceil d/2}1+1, \ldots , S_{d}\}$

1.
2.
then

for

$Ca.sSe$ $Ml$satisfies$\dot{i}f\dot{i}t$

.

holds

$\mathcal{G}$$|\mathcal{H}_{i}|=O(|D_{i}|)$$\mathcal{H}\phi D_{r}$$\mathcal{G}_{i}$$\mathcal{M}_{i}$. Let

and $D_{r}=$and$D_{\ell}=\{S_{1}, \ldots, S\lceil d/2\rceil\}$. Let$\mathcal{H}_{l}=\mathcal{H}\phi D_{\ell}$$\mathcal{H}_{r}=$.

$D’=\{\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H}\ell,D\ell), \mathrm{A}\mathrm{c}\mathrm{F}(\mathcal{H}r’ D_{r})\}$-?,$\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H}, D)=\mathrm{A}\mathrm{C}\mathrm{F}($$If\mathcal{H}s\dot{i}mpl\dot{i}fieS\mathcal{G}$$g_{\dot{i}}ven\mathcal{H}$and $D,$$D’)$.

$\mathrm{A}\mathrm{C}\mathrm{F}(\mathcal{H},D)$This section assumes that is connected.
Let
be a cut vertex of . Let
be the vertex sets of the connected components of. Let be the subgraph of induced by, are the augmented components.
induced by . For each in $M$ , letcontaining ; possibly $t_{h}=0$ .
be the sets in$C_{h}-\{U_{h,1}, \ldots , U_{h,t_{h}}\}$ isis -global if for eachnot -local; otherwise,
is w-local.
$\mathcal{G}$$w$with $D\leq S^{*}$ ,can be computed$S^{*}$

time.

$W_{1},$$\mathcal{G}$$\mathcal{G}-\{w\}$$\mathcal{G}_{i}$$\{w\}\cup W_{i}$$\mathcal{G}_{1},$$\ldots$$\ldots,$$W_{k}$$\mathcal{G}$$g_{k}$$w$$C_{h}$$U_{h,1},$$\ldots,$$U_{h,t_{h}}$$w$$C_{h}$

over a $vf$-set$\dot{i}nO(|\mathcal{H}|+|D|\log(d+1))$

Reducing Case Ml to M2

5$w$$C_{h}$$g_{i},$$C_{h}$$\mathcal{G}_{i}$Lemma 5. 1 1. Assume-local for some . Then,

is
sat-

$C_{h}-\{U_{h,1}, \ldots, U_{h},t_{h}\}$Theorem 3. 8 1. Let be the maximum number
over aof $vf$-sets in any in N. If$vf$-set $S^{*}w\dot{i}thN\leq S^{*}$ , then the $ACF$ problem canbe solved in $O(|\mathcal{H}|+|N|\log(d+q))t_{\dot{i}}me$ .
2. Let be the maximum number of vertex sets
in any in M. Caseof the $CFE$ problem canbe solved $\dot{i}nO(|\mathcal{G}|+|M|\log(d+q))$ time.
$d$$\mathcal{H}S\dot{i}mpl\dot{i}fieS\mathcal{G}$$D_{i}$$d$$M\mathit{3}$$C_{i}$$\mathcal{G}_{i}$$\mathcal{G}_{i}$$\dot{i}sfiesMw\dot{i}thc_{h}$$\mathcal{G}$replaced bysatisfies

iff$\dot{i}sfiesM$$C_{h}-\mathrm{t}Uh,1,$$\mathcal{G}$$\ldots,$.

Then,
sat$Mw\dot{i}thC_{h}$ replaced bysatisfies$C_{h}$$U_{h,t_{h}}\}$

is

$w$

-global.

$\mathcal{G}$.

By Lemma 5. 1 , we may assume that (1) each set
in a -global family in $M$ does not contain and(2) each set in a family in
is -local for some
. Let $H$ be an edge-labeled graph constructed. For
as follows. The vertices of $H$ are$H$ has a cycle
possibly
each -global familyof length 2 where (1) the vertices of are thosesuch that at least one set in
is -local and (2)the edges of are all labeled .
Let
be the blocks of $H$ . Clearly, foreach -global family $C_{h}\in M$ , exactly one blockof $H$ contains all the edges labeled . For each, letbe the family consisting of $\{w\}$ and allis labeledsuch that some edge ofbe the sequencewith $U\in C_{h}$ . For each , letconsisting of the -local families in At as well as
for each
the family
.
with
$w$

$w$

4

Reduction to Case Ml

iff$\mathcal{G}$$(C_{h}-\mathrm{t}U_{h},1, \ldots, U_{h},t_{h}\})$$\cup\{U_{h,1}\cap V(\mathcal{G}i)_{\ldots rt},U_{h},\cap V(h\mathcal{G}i)\}$

2. Assume that$M$$\mathcal{M}$$\mathcal{G}_{i}$$\mathcal{G}_{i}$Let be a graph. Let $V(G)$ denote the set of vertices in . A cut vertex of is one whose removal
increases the number of connected components in; a block is a maximal subgraph with no cut vertex. Let $\Psi(G)$ denote the forest whose vertices are
the cut vertices and the blocks $B$ of and whoseedges are those $\{v, B\}$ with $v\in B.$ $\Psi(G)$ is a tree if
is connected. A set is -local if $U\subseteq V(G)$ . A
family of sets is -local if every set in is G-local.
For a vertex subset $W$ of , let $G-W$ denote thegraph obtained from by deleting the vertices in
$G$

$G$

$G$

$G$

$G$

$v$

$G$

$U$

$G$

$G$

$C$

$C$

$G$

$G$

$W$

.

Let
. A familybe the connected components ofin $M$ is global if for every$\{1, \ldots, k\},$is not -local. Let $H$ be an edgelabeled graph defined as follows. The vertices of $H$$\mathcal{G}_{k}$$\ldots,$$\mathcal{G}_{1},$$\ldots$,$\mathcal{G}_{k}$$\dot{i}\in$$C_{h}$$C_{h}$

are$w$$\mathcal{G}_{k}$$\ldots,$

$C$

$C$

$C_{h}$$C$$B_{1},$$\ldots,$$\mathcal{G}_{i}$$\mathcal{G}_{i}$$C_{h}$$B_{p}$$w$$C_{h}$$B_{j}$$\mathcal{U}_{j}$$U\subseteq V(\mathcal{G})$$C_{h}$$B_{j}$$\mathcal{G}_{i}$$M_{i}$$\mathcal{G}_{i}$$\mathcal{G}_{1},$$\mathcal{G}$$g_{1},$$C_{h},$$\mathcal{G}_{i}$. For each global$C_{h},$$H$

contains acycle possibly of length 2 where (1) the vertices
of $C$ are those such that some set in is -local
and (2) the edges of $C$ are all labeled .
Let
be the blocks of $H$ . Then, foreach global , exactly one contains all the edges$C$$g_{i}$$C_{h}$$C_{h}$$B_{1},$$B_{\mathrm{p}}$$\ldots,$$C_{h}$$\mathcal{U}_{j,i}=\{U\in \mathcal{U}_{j}|U\subseteq V(\mathcal{G}_{i})\}$$\mathcal{G}_{i}\in V(B_{j})$$B_{j}$$B_{j}$$\mathcal{G}_{i}$.

$\mathcal{M}_{i}\mathrm{L}\mathrm{e}\mathrm{m}$ma 5. 2$\mathcal{G}sat_{\dot{i}}sfies\mathcal{M}\dot{i}ff$every$\mathcal{G}_{i}$satisfies

By Lemma 5. 2 , Case Ml can be reduced to Case
M2 in quadratic time. The inefficiency comes fromthe one-by-one removal of cut vertices. Using theunion-find data structure and splay trees, we canremove all the cut vertices in almost linear time.

36
Case M2

6

We here assume$T$$g^{\backslash }\mathrm{i}\mathrm{s}$biconnected, and prove:

Theorem 6. 1 Theorem 2. 2 holds for Case

6.1

$M\mathit{2}$

.

$\mu$

$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$-graph $G$ is an acyclic plane digraph$G$
has exactly one source and exactly
one sink , 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$G$ . A split
component of a split pair $\{u, v\}$ is either
an edge $(u,v)$ or a maximal subgraph $C$ of $G$ suchthat $C$ is a planar $uv$-graph and $\{u, v\}$ is not a
split pair of $C$ . A split pair $\{u, v\}$ of is maxi’
mal if there is no other split pair $\{u’,v\}$
in $G$ with$\{u, v\}$ in a split component of $\{u’,v’\}$ .
The decomposition tree
is a rooted orof
dered tree recursively defined in four cases as follows. The nodes of $T$ are of four types $S,$ $P,$ $Q$ ,and $R$ . Each node of $T$ has an associated planar$st$-graph, called the skeleton of . Also,is associated with an edge in the skeleton of theparent of , called theedge of in.
Case $Q:G$ is a single edge from to . Then, $T$
is a -node whose skeleton is $G$ .
,Case $S:G$ is not biconnected. Letwith $k\geq 2$ be the cut vertices of $G$ . Since $G$ isa planar $st$-graph, each is in exactly two blocks
andwith $s\in G_{1}$ and $t\in G_{k}$ . Then,root is an -node , andconsists of the chain, and the edge $(s, t)$ , where the edge goesfromto$c_{0}=s$ , and $c_{k}=t$ .
Case $P:\{s,t\}$ is a split pair of $G$ with at least
two split components. Then,root is a Pnode , andconsists of $k+1$ parallel edges
from to .
Case : Otherwise. Letwith $k\geq 1$ be the ma[rimal split pairs of $G$ . Let
be the union of the split components of.
Then,root is an -node , andis thesimple triconnected graph obtained from $G$ by replacing eachwith an edge from to and
$st$

$s$

$t$

$G$

$G$

$T$

$\mu$

$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\phi$$\mu$$v\dot{i}rtual$$\mu$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mu$

SPQR decompositions

A planarsuch thathas at least one allocation node.
In the above description of , for each non-leaf
node , an additional edge is added into
between its two poles (which does not correspondto any child of ). . This additional edge has noeffect on our algorithm. From now on, we ignore
this edge in.
For each
in $T,$
is called ablock of $G[2]$ , which differs from that in \S 4 and \S 5.
For a block, let node $(B)=\mu$ . For anancestor of node $(B)$ , the representative of $B$ inis the edge inwhose expansion graphcontains $B$ .
Let
be an R- or -node inwith children. For each $k\in\{1, \ldots, b\}$ , let
be thevirtual edge ofin. If
is an S-node,pert
is a chain consisting of two or more blocks.
Ifis an -nod or -node, pert $(xk)$ is a single
block. For each $k\in\{1, \ldots, b\}$ , we say that theblocks in pert
are on edge . The minor blocksof, those on .
are the blocks on$B=\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{t}(\mu)$$\phi$$\mathrm{s}\mathrm{k}\mathrm{e}(\phi)$$\mathrm{s}\mathrm{k}\mathrm{e}(\phi)$$T$$\mathrm{P}$$\mu$$\chi_{1},$$\ldots,$$e_{k}$$\chi_{b}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\chi_{k}$$\chi_{k}$$(x_{k})$$\mathrm{R}$$\mathrm{P}$$\chi_{k}$$(x_{k})$$e_{k}$$\mathrm{p}\mathrm{e}\mathrm{r}\iota(\mu)$6.2$e_{1},$$e_{b}$$\ldots$

Basic ideas$\mu$$\mathrm{s}\mathrm{k}\mathrm{e}(\phi)$

$\mu$

$t$

$s$

$\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{t}(\mu)$$\mathrm{n}\mathrm{o}\mathrm{n}-\mathrm{S}_{- \mathrm{n}\mathrm{o}\mathrm{d}}\mathrm{e}\mu$Anof a planar graph is an orientation of its edges together with an embedding suchthat the resulting digraph is a planar st-gTaph.
$st- o\mathrm{r}\dot{i}entat_{\dot{i}}on$$\mathrm{Q}$$c_{1},$$\ldots$$c_{k-1}$$\mathfrak{g}$$G_{i+1}$$G_{i}$$T^{j}\mathrm{s}$$\mathrm{S}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mu$$e_{1},$$e_{k}$$\ldots$$e_{i}$$c_{i-1}$$c_{i},$$T’ \mathrm{s}$$\ldots,$$s$$e_{k+1}$

$t$

$R$

$\{s_{1}, t_{1}\},$$\ldots,$$G_{i}$$\{s_{k}, t_{k}\}$$\{s_{i},t_{i}\}$$T’ \mathrm{s}$$\mathrm{R}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mu$$G_{i}$$t_{i}$$s_{i}$$e_{i}$

inserting the edge $(s,t)$ .
In the last three cases, has children
in this order, such that eachis the root of thedecomposition tree of . The virtual edge ofis the edge in.
is called the pertinentgmph pertof as well as the $expanS\dot{i}on$ graphof .
is the pertinent graph ofroot. Also,no child of an -node is an -node, and no child ofa -node is a P-node.
The $alloCat\dot{i}on$ nodes of a vertex of are thenodes of whose skeleton contains ; note that$\chi_{1},$$\mu$$\ldots,\chi_{k}$$\chi_{i}$$G_{i}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$e_{i}$$(\chi_{i})$$e_{i}$

$n$

$s$

$t$

.

$\bullet$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mu$$e_{1},$

Fact 1 (see [2]) If an -vertex planar graph has
an $st$-orientation, then every embedding, where
and are on the exterior face, of this graph can beobtained ffom this orientation through a sequenceof $O(n)$ following operations:
Select one of the two possible flips of an Rnode’s skeleton around its poles.
Permute the skeletons of a P-node’s children
with respect to their common poles.

$\chi_{i}$$G_{i}$$\chi_{i}$$G$$T’ \mathrm{s}$$\mathrm{S}$$\mathrm{S}$$\mathrm{P}$

$v$

$T$

$v$

$G$

$v$

Let
be an edge of . Since is biconnected,
we convert to a planar $st$-graph in $O(n)$ time
for technical convenience. For the remainder of \S 6,
let $T$ be the decomposition tree of . Also, let$\{s, t\}$$\mathcal{G}$$\mathcal{G}$$\mathcal{G}$$\mathcal{G}$$C_{i}=\{U_{i,1}, \ldots, Ui,r_{i}\}$.

Let be a node of T.
denotes the subtreeof rooted at anddenotes the distancefromroot to .
if the vertices ofis contained in pert
are all in pert $(\mu);U_{i,j}$ iscontained in
pert
if in addition, no pole of pert.
is in
Let donebe the deepest node in suchthatis strictly contained in pert , if such anode exists. If no such exists, thencontains
a pole of and let done $(Ui,j)$ beroot.
A family straddles pert
if at least one set
inis strictly contained in pert , and at least
one set in has no vertex in pert .
$T_{\mu}$

$\mu$

.
.

$T$

$\mathrm{d}\mathrm{e}\mathrm{p}(\mu)$$\mu$$T’ \mathrm{s}$$\mu$$(\mu)$$U_{i,j}$$str\dot{i}ctly$$U_{i,j}$$(\mu)$$(\mu)$$(U_{i,\mathrm{j}})$$\mu$$(\mu)$$U_{i,j}$$U_{i,j}$$\mu$$T’ \mathrm{s}$$\mathcal{G}$$C_{i}$$\bullet$$(\mu)$$(\mu)$$C_{i}$$C_{i}$$(\mu)$$U_{i,j}$

$T$

37

.

Let
that for every
is in pert .
Let sub

be the deepest node in $T$ such, at least one vertex of$\mathrm{d}_{\mathrm{o}\mathrm{n}\mathrm{e}}(c_{i})$$\mu$$U_{i,j}\in C_{i}$$U_{i,j}$$(\mu)$.

$\mathrm{f}\mathrm{a}\mathrm{m}(\mu)=\{Ci |\mathrm{d}\mathrm{o}\mathrm{n}\mathrm{e}(C_{i})=\mu\}$If

is a P- or$\mu$$\mathrm{o}\mathrm{f}\mu$.

, where.

and-node, let xfam
and xsubranges over all S-children$(\mu)$$=$$(\mu)=\mathrm{s}\mathrm{u}\mathrm{b}(\mu)\cup$$\chi_{k}$In a fixed embedding of a block $B$ , the polesof $B$ divide the boundary of its exterior face into
two paths, called the twoandsides of B.
is two-sided for $B$ if bothandintersect. In particular,is
two-sided for $B$ if it contains a pole of B.
isside-l (resp., side-2) for $B$ if only
(resp.,
intersects. Assume that $B$ is a minor
block of pert
for some . Let
be the representative of $B$ in. In a fixed embedding ofseparates two faces $F$ and $F’$ . When embedding pert , we can embed
towards
either $F$ or $F’$ , referred to as the twoof $B$ in pert .
A familyis side-O (resp., side-l or side-2)
exterior-forcing for $B$ if done $(ci)$ is an ancestor ofnode $(B)$ in $T$ and somestrictly contained
in $B$ is two-sided (resp., side-l or side-2) for $B$ . For$p=0,1,2$ , define$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{1}(B)$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{2}(B)$$U_{i,j}$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{1}(B)$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{2}(B)$$U_{i,j}$$U_{i,j}$$U_{i,j}$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{1}(B)$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{2}(B))$$U_{i,j}$$(\mu)$$e_{k}$$\mu$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu),$$e_{k}$$(\mu)$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{1}(B)$$or\dot{i}entat_{\dot{i}ons}$$(\mu)$$C_{i}$$U_{i,j}\in C_{i}$.
.

is side-p
exterior-forcing for $B$ }, if there is side-p exteriorforcing for $B$ ;othemise.
$\mathrm{e}\mathrm{x}\mathrm{t}_{p}(B)=\min\{\mathrm{d}\mathrm{e}\mathrm{p}(\mathrm{d}\mathrm{o}\mathrm{n}\mathrm{e}(c_{i}))|C_{i}$$\mathrm{e}\mathrm{x}\mathrm{t}_{p}(B)=\infty$

AssumeLetffom$\neq$$\mathrm{e}\mathrm{x}\mathrm{t}_{p}(B)$$\infty$.

be the path in
to , where). For each$\ell\in\{1, \ldots , h-1\}$ , the representative of $B$ in
must be an exterior edge in any
embedding of. In addition, if $p=1$ or 2, side$p(B)$must be embedded towards the exterior face of theembedding of pert.
Since $(s, t)$ is an edge of , the root of is a Pnode and has a child -node representing $(s,t)$ .
A subtle difference between and each non-root
node of $T$ is that the two sides ofisactually on the same face. To eliminate this difference, we delete from ; afterwards, if has only
one child, we further delete. From here
onwards, denotes this modified tree.
$\mu=\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}(B),$$\phi_{1},$$\phi_{2},$$\ldots,$$\mu$$\phi_{h}$$\mathrm{d}\mathrm{e}_{\mathrm{P}(}\phi_{h}$$T$$\phi h$$=\mathrm{e}_{1}\mathrm{x}\mathrm{t}_{\mathrm{P}}(B)$$\mathrm{s}\mathrm{k}\mathrm{e}(\phi l)$$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}\Psi \mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{s}\mathrm{k}\mathrm{e}(\phi\ell)$$(\phi_{\mathit{1}})$$T$$\mathcal{G}$$\rho$$\mathrm{Q}$$\phi$$\rho$$\mathcal{G}=\mathrm{p}\mathrm{e}\mathrm{r}\mathrm{t}(\rho)$$T$$\phi$$T$$\mu$$(\mu)$$\mathrm{R}$$\mathrm{f}\mathrm{a}\mathrm{m}(\mu)\mathrm{U}(\mathrm{U}_{\chi_{k}}\mathrm{f}\mathrm{a}\mathrm{m}(\chi_{k}))$$( \bigcup_{xk}\mathrm{S}\mathrm{u}\mathrm{b}(\chi_{k}))$

$T$

$\mu$

$(\mu)=\{U_{i,j}|\mathrm{d}_{0}\mathrm{n}\mathrm{e}(Ui,j)=\mu\}$$\bullet$ready nodes of in an arbitrary order. An S-node
is processed when its parent is processed. We detail
how to process as follows.
For the case where is a leaf node of , notethat pert
is a single edge of . Since noisstrictly contained in pert.
Therefore, we simply set
for$p=0,1,2$ ,We next consider the case where is a non-leaf
ready node. Before is processed, an embeddingof every minor block of pert
is already fixed,
except for a possible flip around its poles. Moreover, for each minor block $B$ of pert
and each$p\in\{0,1,2\},$is known. When processing, the CFE algorithm checks whether some embeddingof pertsatisfles the following two
conditions:satisfies every in xfam .
For each straddling pert
and eachstrictly contained in pert , at least one vertexofis embedded on the exterior face of(Remark. This ensures the existence of an embeddingof pertCi later.)
If no such
exists, then cannot
and the CFE algorithm outputs “no” and stops.
Otherwise, it finds such an
and fixes it except
for a possible flip around its poles. It also computes
for $p=0,1,2$ .
To detail how to process , wethe setsin eachinto four types and define a set
for each type as follows.
Type 1:
contains at least one pole of. Then, done
is an ancestor of . Let{ $v\in U_{i,j}|v$ is a vertex in}.
Type 2:
contains at least one vertex but
no pole of. Then, done $(U_{i,j})=\mu$ . Let, as in the case of type 1.
Type 3:is strictly contained in pert
forsome -node of andcontains at least one
vertex in. Then, done $(U_{i,j})=\chi$ . Let{virtual edge of in}.
Type 4:is strictly contained in a minor block$B$ ofpert . Then,
is node $(B)$ or its
descendent. Let{representative of$B$ in ske(p).
Each element ofis called an imageofin. The remainder of \S 6.3 details how
to process of .

$\rho$$\rho \mathrm{h}_{\mathrm{o}\mathrm{m}}T$$T$$\mathcal{G}$$(\mu),$$U_{i,j}$$\mathrm{f}\mathrm{a}\mathrm{m}(\mu)=\mathrm{s}\mathrm{u}\mathrm{b}(\mu)=\emptyset$$\mathrm{e}\mathrm{x}\mathrm{t}_{p}(\mathrm{P}^{\mathrm{e}}\mathrm{r}\mathrm{t}(\mu))=\infty$

$\mu$

$\mu$

$(\mu)$$(\mu)$$\mathrm{e}\mathrm{x}\mathrm{t}_{p}(B)$

$\mu$

..

$(\mu)$$\Phi_{\mu}$$(\mu)$$C_{i}$$\Phi_{\mu}$$(\mu)$$C_{i}$$U_{i,j}\in$$(\mu)$$C_{i}$$U_{i,j}$$\Phi_{\mu}.$$(\mathrm{d}_{\mathrm{o}\mathrm{n}\mathrm{e}}(ci))\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{s}6^{r}\mathrm{i}\mathrm{n}\mathrm{g}$$\Phi_{\mu}$$\mathcal{G}$$\mathrm{s}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{S}\Psi M$$\Phi_{\mu}$$\mathrm{e}\mathrm{x}\mathrm{t}_{p}(\mathrm{P}^{\mathrm{e}}\mathrm{r}\mathrm{t}(\mu))$$\mathrm{c}\mathrm{l}\mathrm{a}\mathrm{S}\mathrm{S}\mathrm{i}\mathrm{f}\mathrm{i}\Gamma$$\mu$$U_{i,j}$$C_{i}$$\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,j}, \mu)$$U_{i,j}$$(U_{i,j})$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mu$$\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,j}, \mu)=$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$U_{i,j}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,\mu)}j$$U_{i,j}$$(\chi)$$\mathrm{S}$$\chi$$\mu$$U_{i,j}$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,j}, \mu)=$$\chi$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$U_{i,j}$$(\mu)$$\mathrm{d}_{0}\mathrm{n}\mathrm{e}(Ui,j)$$\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,j}, \mu)=$$\}$$\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,j}, \mu)$$U_{i,j}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$

$\mu$

6.3

The CFE algorithm

The CFE algorithm processes from bottom up.
A ready node of is either (1) a leaf node or(2) a P- or -node such that theofand the children of every -child of all havebeen processed. The CFE algorithm processes the
$T$

$\mu$

$T$

$\mathrm{R}$$\mu$$\mathrm{n}\mathrm{o}\mathrm{n}- \mathrm{s}_{-_{\mathrm{C}\mathrm{h}}}\mathrm{i}\mathrm{l}\mathrm{d}\mathrm{r}\mathrm{e}\mathrm{n}$$\mathrm{S}$

$\mu$

6.3.1

Processing an S-child

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

$\mu$

38

is a path.
be an -child of . Then,. For eachbe the edges in$k\in\{1, \ldots, b\}$ , let
be the expansion graph of .
Before the -procedure is called on , the following
requirements are met:
For each $k\in\{1, \ldots , b\}$ , an embedding ofhas been fixed, except for a possible flip around its
poles.
$\{1, \ldots, b\}$and $p\in$ {1, 2},
For someis required to face either the left or the.
right side of. Our only choice for embedding pert
is to fliparound their poles. We need to check
whether for some combination of flippings of ,(1) the resulting embedding satisfies every...,and (2) the second requirement aboveis met.
The -procedure consists of the following fivestages:Stage Sl constructs an auxiliary graph $D=$$(V_{D}, E_{D})$ with $V_{D}=\{k_{p}|1\leq k\leq b, p=1,2\}$, insert a path
as follows. For each
into $D$ to connect all $k_{p}\in V_{D}$ such that forandsome type-4. To avoid confusion, we
is side-p for(b)points, and the connectedcall the elements ofcomponents of $D$ clusters. Those points $k_{p}\in V_{D}$is required to face the left side
such that-points. -points are definedcalledareofsimilarly. For each cluster $C$ of $D$ , allranges over all the points in $C$ must be
where. Also,embedded toward the same side ofinvertexaincontains
type-3each. For this reason,
which is on both sides of
constructing $D$ .
whensuch sets were not consideredStage S2 checks whether there is a cluster of $D$
containing both an -point and an -point. Ifsuch a cluster exists, then S2 outputs “no” andstops. Otherwise, each cluster $C$ consists of either -points only or -points only. In the former(resp., latter) case, we call $C$ an -cluster (resp.,
R-duster).
Stage S3 constructs another auxiliary graph$RD=(V_{RD}, E_{RD})\mathrm{h}\mathrm{o}\mathrm{m}D$ as follows.
The vertices of $RD$ are the clusters of $D$ . For each $k\in$$\{1, \ldots, b\}$ , there is an edge
in $RD$ , where$D$) is the cluster of containing point(resp.,(resp., ) . $RD$ may have self-loops.
Stage S4 checks whether $RD$ is bipartite. If
it is not, then S4 outputs “no” and stops. Othemise, for each connected component $K$ of $RD$ ,the clusters in $K$ can be uniquely partitioned intoof clusand
two independent subsets
orcontains both an L-cluster
ters. If
and an -cluster, S4 outputs “no” and stops. Otherwise,
can be partitioned into two indepen-

Let
Let

$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$\mathrm{S}$$\mu$$\chi$$e_{1},$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$e_{b}$$\ldots,$$B_{k}$.

$e_{k}$$\mathrm{S}$$\chi$$B_{k}$$k$$\bullet$$\in$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{p}(B_{k})$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$(\chi)$$B_{1},$$B_{b}$$\ldots,$$B_{1}$$B_{b},$of clusters such thatanddent subsets
and all -clusters are in
all L–clusters are in
is in a cluster in
}
. Let
{
in
cluster
in
is
a
}.
and
{
toward the left side
Stage S5.
for eachof$V_{RD}^{R}$$V_{RD}^{L}$$\mathrm{R}$$V_{RD}^{L}$$V_{D}^{L}=$$V_{RD}^{R}$$V_{RD}^{L}$$k_{\mathrm{p}}|k_{p}$$V_{RD}^{R}$$k_{p}|k_{p}$$V_{D}^{R}=$$\mathrm{e}\mathrm{m}\mathrm{b}\mathrm{e}\Phi \mathrm{S}\mathrm{i}\mathrm{d}\mathrm{e}_{p}(B_{k})$$k_{\mathrm{p}}\in V_{D}^{L}$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$

6.3.2

$\mu$

is an

-node

$\mathrm{R}$is a simple triconnected graphIn this case,beand has a unique embedding. Let
the children of in . For each $k\in\{1, \ldots, b\}$ , letinbe the minor blocks of pert
is an R- or -node, $s_{k}=1$ .
. Whenpert
To process , the CFE algorithm proceeds in fivestages.
$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\chi_{1},$$B_{k,1},$$\ldots,$$\chi_{b}$

$T$

$\mu$

$(\mu)$$B_{k,\epsilon_{k}}$$\ldots,$$\mathrm{P}$$(x_{k})$$\chi_{k}$$\mu$$C_{i}\in \mathrm{f}\mathrm{a}\mathrm{m}(\chi)$$\mathrm{S}$$C_{i}\in \mathrm{f}\mathrm{a}\mathrm{m}(\chi)$$P_{i}$$(\mathrm{a})\mathrm{i}\mathrm{m}\mathrm{g}(U_{i,j}, \chi)=\{e_{k}\}$$U_{i,j}\in C_{i},$$B_{k}$$U_{i,j}$$V_{D}$

6.3.3

$\mu$

is a P-nodeconsists of parallel edges
In this case,, between its two poles with $b\geq 2$ . Let, ...,
be the children of in . For eachbe the minor$k\in\{1, \ldots, b\}$ , let, ...,
embedding
.
When
pert
in
pert
of
blockscan be embedded inthrough, edgesany order. The CFE algorithm first finds a properin three stages. It then tries toembedding of.
on the embedding of
based
pert
embed
$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$e_{1},$ $e_{2},$$\ldots$$e_{b}$$\mu$$\chi_{b}$$\chi_{1}$$(\mu)$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$e_{1}$$T$$B_{k,s_{k}}$$B_{k,1}$$(x_{k})$$e_{b}$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$(\mu)$$\mathrm{s}\mathrm{k}\mathrm{e}(\mu)$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{p}(B_{k})$

$R$

$L$

$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$\mathrm{s}\mathrm{i}\mathrm{d}\mathrm{e}_{p}(B_{k})$$k_{p}$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$U_{i,j}$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$$C_{i}$$\mathrm{s}\mathrm{k}\mathrm{e}(x)$

$L$

$L$

$\mathrm{R}$$\mathrm{R}$$L$$\{C_{1}, C_{2}\}$$C_{2}$$C_{1}$$k_{2}$$k_{1}$$V_{K,1}$$V_{K,1}$$\mathrm{R}$$V_{RD}$$V_{K,2}$$V_{K,2}$References[1] Z.-Z. Chen, M. Grigni and C.H. Papadimitriou. Planar Map Graphs. In Proceedings ofthe 30th Annual ACM Symposium on Theoryof Computing, pp. 514-523, 1998.

[2] G. Di Battista and R. Tamassia. On-Line Planarity Testing. SIAM J. Comput., $25(5):956-$
997, 1996.