Information Technology Reference
In-Depth Information
width and height of the drawing is very challenging, researchers have also focused
their attention on optimizing one dimension of the drawing [6,11,13,17], while
the other dimension is unbounded. In this paper we develop new techniques
that can produce drawings with small height. We distinguish between the terms
'plane' and 'planar'. A
plane graph
is a planar graph with a fixed combinatorial
embedding and a specified outer face. While drawing a planar graph, we allow
the output to represent any planar embedding of the graph. On the other hand,
while drawing a plane graph, the output is further constrained to respect the
input embedding.
State-of-the-art algorithms that compute straight-line drawings of
n
-vertex
plane graphs on an (
O
(
n
)
2
n/
3)-size grid imply an upper bound of 2
n/
3on
the height of straight-line drawings [5,6]. This bound is tight for plane graphs,
i.e., there exist
n
-vertex plane graphs such as plane nested triangles graphs
and some plane 3-trees that require a height of 2
n/
3 in any of their straight-
line drawings. Recall that an
n
-vertex
nested triangles graph
is a plane graph
formed by a sequence of
n/
3 vertex disjoint cycles,
C
1
,
C
2
,...,
C
n/
3
,wherefor
each
i
×
,cycle
C
i
contains the cycles
C
1
,...,
C
i−
1
in its interior, and
a set of edges that connect each vertex of
C
i
to a distinct vertex in
C
i−
1
. Besides,
a
plane
3
-tree
is a triangulated plane graph that can be constructed by starting
with a triangle, and then repeatedly adding a vertex to some inner face of the
current graph and triangulating that face.
The 2
n/
3 upper bound on the height is also the currently best known bound
for polyline drawings, even for planar graphs, i.e., when we are allowed to choose
a suitable embedding for the output drawing. Frati and Patrignani [10] showed
that in the variable embedding setting, an
n
-vertex nested triangles graph can
bedrawnwithheightatmost
n/
3+
O
(1), which is significantly smaller than
the lower bound of 2
n/
3 in the fixed embedding setting. Similarly, Hossain et
al. [11] showed that an
universal set
of
n/
2 horizontal lines can support all
n
-
vertex planar 3-trees, i.e., every planar 3-tree admits a drawing with height at
most
n/
2. They also showed that 4
n/
9 lines suce for some subclasses of planar
3-trees, and asked whether 4
n/
9 is indeed an upper bound for planar 3-trees.
In the context of optimization, Dujmovic et al.[9] gave fixed-parameter-
tractable (FPT) algorithms, parameterized by pathwidth, to decide whether a
planar graph admits a straight-line drawing on
k
horizontal lines. Drawings with
minimum number of parallel lines have been achieved for trees [13]. Recently,
Biedl [2] gave an algorithm to approximate the height of straight-line drawings
of 2-connected outerplanar graphs within a factor of 4.
∈{
2
,...,n/
3
}
Contributions.
In this paper we show that every
n
-vertex planar graph with
maximum degree
Δ
, having a simple cycle separator of size
ʻ
, admits a drawing
with height 4
n/
9+
O
(
ʻΔ
), which is better than the previously best known bound
of 2
n/
3 for any
ʻΔ
o
(
n
). This result is an outcome of a new application of
the planar separator theorem [8]. Although the technique is simple, it has the
potential to be a powerful tool while computing compact drawings for planar tri-
angulations in the variable embedding setting. If the input graphs are restricted
to planar 3-trees, then we can improve the upper bound to 4
n/
9+
O
(1), which
∈