Information Technology Reference
In-Depth Information
···
Fig. 5.
Atreeforwhich
|R|
=
|S|
=14
n/
17. The set
R
is colored black.
The greedy algorithm achieves exactly this amount on the tree depicted in Fig. 5.
Note that also
|
S
|
=
c
0
+
c
1
=14
n/
17 in this tree. In general, Theorem 1 is close
to best possible:
Theorem 2.
For any >
0
and any n>
2
/
+5
, there exists a tree T with n
vertices in which every column planar subset in T has at most
(5
/
6+
)
n vertices.
Proof.
Let
p
=
.Let
T
be
p
copies,
T
1
,T
2
,...,T
p
,ofthetreeshownin
Fig. 6a in which the root of
T
i
+1
is made a child of the rightmost leaf of
T
i
,for
i
=1
,...,p
n/
6
−
1. Suppose there is a column planar set
R
of marked vertices in
T
with
subtrees
T
i
,T
i
+1
,...,T
j
there must be at least two trees with 6 marked vertices and the
other trees with 5 marked vertices. If not, since each subtree has 6 vertices, the
average fraction of marked vertices per tree is less than
5
k
+2
|
R
|
/n >
5
/
6+
. Then in some sequence of at most
k
=
1
/
(3
)
6
k
<
5
/
6+
.
Let
T
i
,T
i
+1
,...,T
j
be such a sequence. By possibly deleting a prefix of the
sequence, we can assume that
T
i
has 6 marked vertices. Let
>i
be the smallest
index such that the root of
T
is marked. Since
T
i
,T
i
+1
,...,T
j
contains at least
two trees with 6 marked vertices,
T
exists. Let
H
be the subtree induced by the
root of
T
and the vertices in
T
i
∪ T
i
+1
∪···∪T
−
1
. By definition, the unmarked
vertices in
H
are exactly the roots of the subtrees
T
i
+1
,T
i
+2
,...,T
−
1
. We claim
that the marked vertices are not column planar in
H
.
To simplify notation, let
H
1
,H
2
,...,H
q−
1
be the sequence of subtrees in
H
and let
r
q
bethe(marked)rootof
T
. Label the vertices of
H
i
as in Fig. 6a
subscripted by
i
. See Fig. 6b. Let
R
be the marked vertices in
H
and suppose
R
is
ˁ
-column planar in
H
. For an edge
R
,let
ˁ
(
a, b
)=
{
a, b
}
in
H
with
a, b
∈
r
1
r
2
r
s
t
u
v
r
q−
1
r
q
s
1
t
1
u
1
v
1
w
···
w
1
H
1
H
2
H
q−
1
(a)
(b)
Fig. 6.
(a) The tree
T
i
and (b)
H
used in the proof of Theorem 2
