Information Technology Reference
In-Depth Information
Proof.
By exchanging the roles of
x
-and
y
-coordinates in the definition of col-
umn planar, we see that for all injections
ʳ
:
R
ₒ
R
, there exists a plane
straight-line embedding of
G
1
with
v
∈
R
at (
ʳ
(
v
)
,ˁ
(
v
)). Since
G
2
is a ULP
graph, for all injections
y
:
V
ₒ
R
, there exists an injection
x
:
V
ₒ
R
such that
placing
v
V
at (
x
(
v
)
,y
(
v
)) results in a straight-line embedding of
G
2
.Thus,
placing the vertices
v
∈
∈
R
at (
x
(
v
)
,ˁ
(
v
)) permits both a straight-line embedding
of
G
1
and
G
2
.
Combining this with Theorem 1 yields
Corollary 2.
A tree and a ULP graph admit a
14
n/
17
-PSGE.
Two outerpaths & outerpath and tree.
An
outerplanar
graph is a planar
graph that admits an embedding (called the
outerplane
embedding) that places
all its vertices on the unbounded face. An
outerpath
is an outerplanar graph
whose
weak dual
(the graph obtained from the dual graph by deleting the ver-
tex corresponding to the unbounded face) is a path. A maximal outerpath has
exactly two vertices of degree two: these vertices are on the faces that corre-
spond to the terminal vertices of the dual path. Consider a maximal outerpath
G
=(
V,E
). The
outer cycle
of
G
is the Hamiltonian cycle of
G
that bounds the
unbounded face in the outerplane embedding of
G
.Denoteby
C
(
G
) the vertices
of degree two in
G
. Deleting
C
(
G
)from
G
partitions the outer cycle of
G
into
two connected components whose vertices we refer to as
A
(
G
)and
B
(
G
). Note
that
A
(
G
)
∪
B
(
G
)
∪
C
(
G
)=
V
. It is easy to see that:
Lemma 4.
Given a maximal outerpath G
=(
V,E
)
, the subsets A
(
G
)
∪
C
(
G
)
and B
(
G
)
∪
C
(
G
)
are column planar.
Unlike in the tree setting, Theorem 3 does not immediately give a lower bound
on the size of a PSGE of two outerpaths, since we might have
|A
(
G
)
|
=
|B
(
G
)
|
=
n/
2
−
1. Fortunately, this is easily resolved:
Theorem 4.
Every two outerpaths on a set of n vertices admit an n/
4
-PSGE.
Proof.
Consider outerpaths
G
1
=(
V,E
1
)and
G
2
=(
V,E
2
). Without loss of
generality,
G
1
and
G
2
are maximal. Let
X
i
C
(
G
i
)for
X
=
A, B
and
i
=1
,
2. Then by Theorem 3 and Lemma 4,
G
1
and
G
2
admit a max
:=
X
(
G
i
)
∪
A
1
∩
{|
A
2
|
A
1
∩
B
2
|
B
1
∩
A
2
|
B
1
∩
B
2
|}
-PSGE. Since the union of these four sets
is again
V
, the maximum of their cardinalities must be at least
n/
4.
,
|
,
|
,
|
Since
|
C
(
G
)
|
+max
{|
A
(
G
)
|
,
|
B
(
G
)
|} ≥
n/
2 + 1, Theorem 1 and 3 yield:
Corollary 3.
An outerpath and a tree on n vertices admit a
11
n/
34
-PSGE.
