Information Technology Reference
In-Depth Information
lemma can be derived from the known straight-line [5] and polyline drawing
algorithms [4]. We omit the proof due to space constraints.
Lemma 2.
Let G be an n-vertex plane triangulation and let v
1
,v
n
,v
2
be the
outer vertices of G in clockwise order on the outer face. Assume that T
v
n
has
at most p leaves. Then for any placement of v
n
on line l
1
or l
p
+2
,thereexistsa
straight-line drawing ʓ of G on L
p
+2
such that v
2
and v
1
lie on lines l
p
+2
and
l
1
, respectively.
Chrobak and Nakano [6] showed that every planar graph admits a straight-
line drawing with height 2
n/
3. We now observe some properties of Chrobak and
Nakano's algorithm [6]. Let
G
be a plane triangulation with
n
vertices and let
x, y
be two user prescribed outer vertices of
G
in clockwise order. Let
ʓ
be the
drawing of
G
produced by the Algorithm of Chrobak and Nakano [6]. Then
ʓ
has the following properties:
(CN
1
)
ʓ
is a drawing on
L
q
,where
q
2
n/
3.
(CN
2
) For the vertices
x
and
y
,wehave
l
(
x
)=
l
1
and
l
(
y
)=
l
q
in
ʓ
.The
remaining outer vertex
z
lies on either
l
1
or
l
q
.
Note that the user cannot choose the placement of
z
, i.e., the algorithm may
produce a drawing where
l
(
x
)=
l
1
,l
(
y
)=
l
q
and
l
(
z
)=
l
1
, however, this does
not imply that there exists another drawing where
l
(
x
)=
l
1
,l
(
y
)=
l
q
and
l
(
z
)=
l
q
. We end this section with the following lemma.
Lemma 3.
Let G be a plane graph and let ʓ be a straight-line drawing of G on
k horizontal lines, but the lines are not necessarily equally spaced. Then there
exists a drawing ʓ
of G on a set of k horizontal lines that are equally spaced.
Furthermore, for every i
≤
, the left to right order of the vertices on
the ith line in ʓ coincides with that of ʓ
.
Proof (Outline).
One can construct
ʓ
by first transforming
ʓ
intoa'flat-
visibility representation' on equally spaced horizontal lines, as shown in Fig-
ures 1(d)-(e), and then transforming this representation again into a straight-
line drawing [1,3].
∈{
1
,
2
,...,k
}
In the following sections we describe our drawing algorithms. Note that for
simplicity we often omit the floor and ceiling functions while defining different
parameters of the algorithms. One can describe a more careful computation using
proper floor and ceiling functions, but that does not affect the asymptotic results
discussed in this paper.
3 Drawing Triangulations with Small Height
Let
G
=(
V,E
)bean
n
-vertex planar triangulation and let
ʓ
be a planar drawing
of
G
on the Euclidean plane. Let
C
=(
V
c
,E
c
) be a simple cycle separator of
G
of size
ʻ
.Let
G
i
=(
V
i
,E
i
) be the graph induced by the vertices that lie
inside
C
and on the boundary of
C
. Similarly, let
G
o
=(
V
o
,E
o
) be the graph
induced by the vertices that lie outside
C
and on the boundary of
C
. Specifically,
V
=
V
i
∪
V
o
,
E
=
E
i
∪
E
o
,
V
i
∩
V
o
=
V
c
,and
E
i
∩
E
o
=
E
c
.Wenowcomputea
polyline drawing of
G
.
