Information Technology Reference
In-Depth Information
3.1 Exponential Width
Pach and Toth did not analyze what happens to the width during the transfor-
mation. In fact, they did not even worry about achieving integer coordinates,
but it is clear that this can be done with minor modifications. One can show
that the width must increase exponentially for some graphs:
v
v
a
1
a
3
a
1
a
3
4
4
a
d
a
d
3
3
2
2
a
2
a
4
a
2
a
4
1
1
u
u
Fig. 2.
(Left) A planar graph. (Right) Inserting vertices into inner faces.
Lemma 1.
Let ʓ be the drawing in Fig. 2(left). Any planar straight-line drawing
ʓ
that preserves the y-coordinates and left-to-right-orders of ʓ has width at least
1
3
2
d
+1
.
Proof.
Denote by
x
(
w
)the
x
-coordinate of vertex
w
in
ʓ
. Assume that
x
(
v
)
≤
x
(
u
); the other case is proved similar and in fact gives an even larger width
bound. For ease of arithmetic operations, assume the drawing has been translated
so that
x
(
v
) = 0. One can now show by induction on
i
(details are omitted) that
1
3
(
x
(
u
)+2
2
i
)
1
3
(2
x
(
u
)+2
2
i
+1
)
x
(
a
2
i−
1
)
≥
−
1 d
x
(
a
2
i
)
≥
−
1
for
i
≥
1. This implies the result.
Theorem 2.
There exists a graph H that has a planar straight-line drawing of
height 4, but any such drawing has width at least
3
2
n/
3
.
Proof.
The graph
H
is obtained by taking the graph
G
from Fig. 2(left) with
d
a new vertex adjacent
to the three vertices of the face. Note that
H
is triangulated and has 3
d
vertices.
It has a
y
-monotone poly-line drawing on four rows (see Fig. 2(right)), and hence
byThm.1alsoastraight-linedrawingon4rows.
Let
ʓ
H
be an arbitrary planar straight-line drawing of
H
that uses four rows.
Let
ʓ
G
be the induced planar straight-line drawing of
G
. One can argue (details
are omitted) that
ʓ
G
−
≥
11 and inserting into each inner face except
{
u,v,a
1
}
a
d
preserves, after possible horizontal and vertical flips,
the
y
-coordinates and left-to-right-orders of the drawing of Fig. 2(left). Hence it
requires width at least
3
2
d
by the previous lemma and
ʓ
H
cannot be smaller.
One can easily show that
H
requires at least 4 rows in
any
straight-line draw-
ing. Thm. 2 hence has the following consequence:
Corollary 1.
There exists an infinite class of planar graphs such that any pla-
nar straight-line drawing that has optimal height has exponential area.
