Information Technology Reference
In-Depth Information
Theorem 1.
Let G be an n-vertex planar graph with maximum degree Δ.If
G contains a simple cycle separator of size ʻ,thenG admits a
4
-bend polyline
drawing with height
4
n/
9+
O
(
ʻΔ
)
and at most
4
ʻΔ bends in total.
Since every planar triangulation has a simple cycle separator of size
O
(
√
n
)[8],
we obtain the following corollary.
Corollary 1.
Every n-vertex planar triangulation with maximum degree o
(
√
n
)
admits a polyline drawing with height at most
4
n/
9+
o
(
n
)
.
Pach and Toth [15] showed that polyline drawings can be transformed into
straight-line drawings while preserving the height if the polyline drawing is mono-
tone, i.e., if every edge in the polyline drawing is drawn as a
y
-monotone curve.
Unfortunately, our algorithm does not necessarily produce monotone drawings.
4 Drawing Planar 3-Trees with Small Height
In this section we examine straight-line drawings of planar 3-trees.
4.1 Technical Background
Let
G
be an
n
-vertex planar 3-tree and let
ʓ
be a straight-line drawing of
G
.
Then
ʓ
can be constructed by starting with a triangle, which corresponds to the
outer face of
ʓ
, and then iteratively inserting the other vertices into the inner
faces and triangulating the resulting graph. Let
a,b,c
be the outer vertices of
ʓ
in clockwise order. If
n>
3, then
ʓ
has a unique vertex
p
that is incident to all
the outer vertices. This vertex
p
is called the representative vertex of
G
.
For any cycle
i,j,k
in
G
,let
G
ijk
be the subgraph induced by the vertices
i,j,k
and the vertices lying inside the cycle. Let
G
ijk
be the number of vertices
in
G
ijk
. The following two lemmas describe some known results.
Lemma 4 (Mondal et al. [14]).
Let G be a plane
3
-tree and let i,j,k be a
cycle of three vertices in G.ThenG
ijk
is a plane
3
-tree.
Lemma 5 (Hossain et al. [11]).
Let G be an n-vertex plane
3
-tree with
the outer vertices a,b,c in clockwise order. Let D be a drawing of the outer
cycle a,b,c on L
n
, where the vertices lie on l
1
, l
k
and l
i
with k
≤
n and
i
.ThenG admits a straight-line drawing ʓ on L
k
,where
the outer cycle of ʓ coincides with D.
∈{
l
1
,l
2
,l
n
,l
n−
1
}
Let
G
be a plane 3-tree and let
a,b,c
be the outer vertices of
G
. Assume that
G
has a drawing
ʓ
on
L
k
,where
a, b
lie on lines
l
1
,l
k
, respectively, and
c
lies on
line
l
i
,where1
≤
i
≤
k
. Then the following properties hold for
ʓ
[11].
Reshape.
Let
p,q
and
r
be three different points on lines
l
1
,l
k
and
l
i
, respec-
tively. Then
G
has a drawing
ʓ
on
L
k
such that the outer face of
ʓ
coincides
with triangle
pqr
(e.g., Figures 3(a)-(b)).
