Information Technology Reference
In-Depth Information
r
s
1
s
2
s
1
r
1
r
1
r
2
r
r
(a)
(b)
(c)
Fig. 3.
Embedding a tree with a column planar set. The column planar vertices are black.
4]. By (i), and possibly after mirroring the embedding of the subtree rooted at
r
1
horizontally, the edge
does not cross edges in the subtree rooted at
r
1
.
Embed
s
1
at
x
=
+2.Let
T
1
,...,T
k
be the child subtrees of
s
1
.Embed
T
i
recursively and scale its
x
-coordinates to lie in [
+3+2
i,
+4+2
i
] for all
1
{
r, r
1
}
for other
ʳ
.Ifitisabove,let
r
(
T
1
)
,...,r
(
T
k
) have progressively larger
y
-coordinates (by
scaling up and mirroring vertically if necessary). If it is below, let them have
progressively smaller
y
-coordinates. Then none of the edges
≤
i
≤
k
.Vertex
s
1
will be above
{
r, r
1
}
for some
ʳ
and below
{
r, r
1
}
{
s
1
,r
(
T
i
)
}
cross
{
does not cross any edges in
T
i
by (i) and (ii).
Recursively, embed the remaining child subtrees
T
1
,...,T
t
(none of whose
roots are in
R
) with
x
-coordinates in [
+3+2
k
+2
i,
+4+2
k
+2
i
] for all
1
r, r
1
}
and the edge
{
s
1
,r
(
T
i
)
}
t
such that
r
(
T
1
)
,...,r
(
T
t
) have progressively larger
y
-coordinates. The
≤
i
≤
does not cross any edges in
T
i
by (ii). In the completed drawing,
note that
r
has the lowest
x
-coordinate, and thus (i) is satisfied. Properties (ii)
and (iii) are trivially satisfied.
Suppose that
p
(
T
)
r, r
(
T
i
)
edge
{
}
∈
R
. Proceed first as in the previous case. Suppose
C
R
(
v
)
ↆ
and
C
R
(
v
)
{
. Mirror the recursive embedding of the
subtree rooted at
r
2
horizontally and scale it to have
x
-coordinates in [
r
1
,r
2
,s
1
,s
2
}
ↆ{
r
1
,r
2
}
−
3
,
−
2].
Embed the subtree rooted at
s
1
as in the previous case. For
s
2
, proceed similarly
but embed
s
2
and its subtree to the left of
r
. See Fig. 3b. Properties (i)-(iii) are
trivially satisfied.
Finally, suppose that
r
=
r
(
T
)
R
. Embed its child subtrees
T
1
,...,T
t
to
have
x
-coordinates in [2
i,
2
i
+ 1] for all 1
∈
t
, starting with the ones rooted
at a vertex in
R
.Embed
r
suciently high on the line
x
= 1. For subtrees
T
i
with
r
(
T
i
)
≤
i
≤
∈
R
, note that the edge
{
r, r
(
T
i
)
}
does not cross any edges of
T
i
due
to (iii). For the other ones,
does not cross edges of
T
i
due to (i) and
(ii). See Fig. 3c. Properties (i-iii) are satisfied.
{
r, r
(
T
i
)
}
It remains to show that every tree contains a subset that satisfies the conditions
imposed by Lemma 1. We show that every tree on
n
vertices contains such a
subset of size at least 14
n/
17 and that there are trees with no column planar
