Abstract:
A layered drawing of a planar graph G is a planar straight-line drawing of
G, where the vertices are placed on a set of horizontal lines, called layers. A
minimum-layer drawing of G is a layered drawing of G with the minimum number
of layers among all the layered drawings of G. To the best of our knowledge,
no polynomial-time algorithm is known till now to construct a minimum-layer
drawing of a general planar graph. Even for a restricted class of layered drawings,
where the edges are between vertices on adjacent layers, the problem of
recognizing graphs to admit such a drawing is in NP-complete. Therefore, layered
drawings of graphs are often studied for special classes of planar graphs.
In this thesis we address the problem of minimum-layer drawing of trees.
For a tree T with pathwidth h, a linear-time algorithm is already known and it
produces a drawing of T on ⌈3h/2⌉ layers. However, the drawing obtained by
this algorithm is not necessarily a minimum-layer drawing of T. A necessary
condition for a tree to admit a k-layer drawing is also known and this condition
is also sufficient for k ≤ 2. However for k > 2, there is no such necessary and
sufficient characterization. The problem of finding a minimum-layer drawing
of a tree is known to be in NP-hard with some constraints for the placement
of vertices. There are also some polynomial-time algorithms for obtaining a
minimum-layer drawing of T with some other constraints on the placement of
vertices. However for the general version of the problem, there is neither any
polynomial-time algorithm or any hardness result known so far. In this paper
we give a linear-time algorithm for obtaining a minimum-layer drawing of a
tree. We first give a linear-time algorithm to obtain a minimum-layer drawing
of a rooted tree with the additional constraint that the root of the tree is visible
from outside the bounding box of the drawing. Using this algorithm, we then
give an algorithm to find a minimum-layer drawing of a tree in linear time.
