Minimum - layer drawings of trees

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.