Information Technology Reference
In-Depth Information
Drawing Planar Graphs with Reduced Height
Stephane Durocher
and Debajyoti Mondal
Department of Computer Science, University of Manitoba, Canada
{
durocher,jyoti
}
@cs.umanitoba.ca
Abstract.
A straight-line (respectively, polyline) drawing
ʓ
of a planar
graph
G
on a set
L
k
of
k
parallel lines is a planar drawing that maps each
vertex of
G
to a distinct point on
L
k
and each edge of
G
to a straight line
segment (respectively, a polygonal chain with the bends on
L
k
) between
its endpoints. The height of
ʓ
is
k
, i.e., the number of lines used in the
drawing. In this paper we compute new upper bounds on the height of
polyline drawings of planar graphs using planar separators. Specifically,
we show that every
n
-vertex planar graph with maximum degree
ʔ
,
having a simple cycle separator of size
ʻ
, admits a polyline drawing with
height 4
n/
9+
O
(
ʻʔ
), where the previously best known bound was 2
n/
3.
Since
ʻ ∈ O
(
√
n
), this implies the existence of a drawing of height at
most 4
n/
9+
o
(
n
) for any planar triangulation with
ʔ ∈ o
(
√
n
). For
n
-vertex planar 3-trees, we compute straight-line drawings with height
4
n/
9+
O
(1), which improves the previously best known upper bound of
n/
2. All these results can be viewed as an initial step towards compact
drawings of planar triangulations via choosing a suitable embedding of
the input graph.
1 Introduction
A
polyline drawing
of a planar graph
G
is a planar drawing of
G
such that each
vertex of
G
is mapped to a distinct point in the Euclidean plane, and each edge is
mapped to a polygonal chain between its endpoints. Let
L
k
=
{
l
1
,l
2
,...,l
k
}
be a
set of
k
horizontal lines such that for each
i
k
, line
l
i
passes through the point
(0
,i
). A polyline drawing of
G
is called a
polyline drawing on L
k
if the vertices
and bends of the drawing lie on the lines of
L
k
.The
height
of such a drawing is
k
,
i.e., the number of parallel horizontal lines used by the drawing. Such a drawing is
also referred to as a
k-layer drawing
in the literature [13,18]. Let
ʓ
be a polyline
drawing of
G
.Wecall
ʓ
a
t-bend polyline drawing
if each of its edges has at most
t
bends. Thus a 0-bend polyline drawing is also known as a
straight-line drawing
.
Drawing planar graphs on a small integer grid is an active research area in graph
drawing [7,16], which is motivated by the need of compact layout of VLSI circuits
and visualization of software architecture. Since simultaneously optimizing the
≤
Work of the author is supported in part by the Natural Sciences and Engineering
Research Council of Canada (NSERC).
Work of the author is supported in part by a University of Manitoba Graduate
Fellowship.
