Information Technology Reference
In-Depth Information
h
h
h
e
g
f
g
g
f
c
e
d
e
d
f
b
d
b
c
a
c
a
a
b
(a)
(b)
(c)
Fig. 1.
(a) A planar graph
G
. (b)-(c) Two polyline drawings of
G
seems to be an elusive goal. For example, every planar triangulation with
n
vertices admits a straight-line drawing (i.e., a 0-bend polyline drawing) in
O
(
n
2
)
area [9]. Several improvements on the constant hidden in
O
(
.
) notation have been
achieved [2,4,9,17], and the best known bound is 8
n
2
/
9=0
.
89
n
2
[4]. Better upper
bounds, i.e., 4
n
2
/
9
<
0
.
45
n
2
, can be attained if we use 1-bend polyline drawings,
which takes at most 2
n/
3 bends in total [20]. Although these drawings require
small area, the compactness comes at the expense of bad angular resolution, i.e.,
ʩ
(1
/n
). Garg and Tamassia [19] showed that there exists planar graphs such
that any of its straight-line drawing with angular resolution
ʩ
(1
/ˁ
)requires
at least
ʩ
(
c
ˁn
)area,where
c>
1, which suggests that drawings with angular
resolution
ʩ
(1
/Δ
) and polynomial area may exist only if we allow the edges to
have bends.
Allowing bends helps both to reduce area and to improve angular resolution,
e.g., given an
n
-vertex planar graph with maximum degree
Δ
, one can construct
a 3-bend polyline drawing with 2
/Δ
radians of resolution and 3
n
2
area [13]. The
angular resolution can be improved to
ʩ
(1
/d
(
v
)) radians (for each vertex
v
)
with an expense of higher area [10,12], which also helps to reduce the number of
bends per edge. Table 1 presents a brief summary of the related results.
Tabl e 1.
Angular resolution, area and total bends in
k
-bend polyline drawings, where
ʱ ∈
[1
/
4
,
1
/
2], and
ʲ ∈
[1
/
3
,
1].
Graph Class
Area
Resolution
k
-Bends T. Bends Reference
7
n
2
/
8
ʩ
(1
/n
2
)
Maximal Planar
0
0
[4]
9
n
2
/
2
Maximal Planar
ʩ
(1
/n
)
0
0
[16]
12
.
5
n
2
Maximal Planar
0
.
5
/d
(
v
)
1
3
n
[10]
450
n
2
Maximal Planar
1
/d
(
v
)
1
3
n
[5]
4
n
2
/
9
ʩ
(1
/n
2
)
Maximal Planar
1
2
n/
3
[20]
200
n
2
Maximal Planar
1
/d
(
v
)
2
6
n
[12]
ʱ
(
d
(
v
)(
ʱ
2
+1
/
4)
Maximal Planar (6
ʱ
+8
/
3)
2
n
2
2
5
.
5
n
Theorem 2
ʲ
(
d
(
v
)(
ʲ
2
+1)
Maximal Planar (6
ʲ
+2
/
3)
2
n
2
2
5
.
5
n
Theorem 3
6
n
2
3-connected Planar
2
/ʔ
5
n −
15
3
[15]
3
n
2
General Planar
2
/ʔ
3
5
n −
15
[13]
