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
 
Search WWH ::




Custom Search