Information Technology Reference
In-Depth Information
The reductions described in Theorems 1 and 2 can be modified so that (
V,E
) consists
of a set of paths (by removing levels
V
0
and
V
1
), or that (
V,E
) is a 2-connected series-
parallel graph (by introducing levels
V
2
m
+2
and
V
2
m
+3
“symmetric” to levels
V
1
and
V
0
, respectively).
3 Polynomial-Time Algorithms
In this section we prove that both
T
-L
EVEL
P
LANARITY
and CL-P
LANARITY
are
polyomial-time solvable problems if restricted to proper instances.
3.1
T
-L
EVEL
P
LANARITY
We start by describing a polynomial-time algorithm for
T
-L
EVEL
P
LANARITY
.The
algorithm is based on a reduction to the
Simultanoues Embedding with Fixed Edges
problem for two graphs (SEFE-2), that is defined as follows.
A
simultanoues embedding with fixed edges
(SEFE) of two graphs
G
1
=(
V,
E
1
) and
G
2
=(
V,
E
2
) on the same set of vertices
V
consists of two planar drawings
ʓ
1
and
ʓ
2
of
G
1
and
G
2
, respectively, such that each vertex
v
V
is mapped to the same point in
both drawings and each edgeofthe
commongraph
G
∩
=(
V,
E
1
∩
∈
E
2
) is represented
by the same simple curve in the two drawings. The SEFE-2 problem asks whether a
given pair of graphs
admits a SEFE [5]. The computational complexity of the
SEFE-2 problem is unknown, but there exist polynomial-time algorithms for instances
that respect some conditions [2,5,6,7,12]. We are going to usearesult by Blasiusand
Rutter [7], who proposed a quadratic-time algorithm for instances
G
1
,
G
2
of SEFE-2
in which
G
1
and
G
2
are 2-connected and the common graph
G
∩
is connected.
In the analysis of the complexity of the following algorithms we assume that the in-
ternal nodes of the trees in
G
1
,
G
2
) of
T
-L
EVEL
P
LANARITY
and of tree
T
in any instance (
V,E,ʳ,T
) of CL-P
LANARITY
have at least two chil-
dren. It is easily proved that this is not a loss of generality; also, this allows us to describe
the size of the instances in terms of the size of their sets of vertices.
T
in any instance (
V,E,ʳ,
T
Lemma 1.
Let
(
V,E,ʳ,T
)
be a proper instance of
T
-L
EVEL
P
LANARITY
.There
exists an equivalentinstance
of SEFE-
2
such that
G
1
=(
V
∗
,
E
1
)
and
G
2
=
(
V
∗
,
E
2
)
are
2
-connected andthecommongraph
G
∩
=(
V
∗
,
E
1
∩
G
1
,
G
2
E
2
)
is connected.
G
1
,
G
2
Further, instance
can be constructed in lineartime.
G
1
,
G
2
Proof:
We describe how to construct instance
. Refer to Fig.3.
=
t
1
,t
2
,...,t
k
,q
k
,p
k
,q
k−
1
,p
k−
1
,...,q
1
,p
1
,where
k
is the number of levels of (
V,E,ʳ,
Graph
G
∩
contains a cycle
C
T
). For each
i
=1
,...,k
, graph
G
∩
contains
acopy
T
i
of tree
T
i
∈T
, whose root is vertex
t
i
, and contains two stars
P
i
and
Q
i
centered at vertices
p
i
and
q
i
, respectively, whose number of leaves is determined as
follows. For each vertex
u
∈
V
i
such that an edge (
u,v
)
∈
E
exists connecting
u
to a
vertex
v
∈
V
i−
1
,star
P
i
contains a leaf
u
(
P
i
); also, for each vertex
u
∈
V
i
such that
an edge (
u,v
)
V
i
+1
,star
Q
i
contains a leaf
u
(
Q
i
). We also denote by
u
(
T
i
) a leaf of
T
i
corresponding to vertex
u
∈
E
exists connecting
u
to a vertex
v
∈
V
i
.
Graph
G
1
contains
G
∩
plus the following edges. For
i
=1
,...,k
, consider each
vertex
u
∈
V
i
.Suppose that
i
is even. Then,
G
1
has an edge connecting the leaf
u
(
T
i
)
of
T
i
corresponding to
u
with either the leaf
u
(
Q
i
) of
Q
i
corresponding to
u
, if it exists,
∈
