Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Minimum-Layer Upward Drawings of Trees
Muhammad Jawaherul Alam, Md. Abul Hassan Samee, Mashfiqui Rabbi, and Md. Saidur Rahman
Vol. 14, no. 2, pp. 245-267, 2010. Regular paper.
Abstract An upward drawing of a rooted tree T is a planar straight-line drawing of T where the vertices of T are placed on a set of horizontal lines, called layers, such that for each vertex u of T, no child of u is placed on a layer vertically above the layer on which u has been placed. In this paper we give a linear-time algorithm to obtain an upward drawing of a given rooted tree T on the minimum number of layers. Moreover, if the given tree T is not rooted, we can select a vertex r of T in linear time such that an upward drawing of T rooted at r would require the minimum number of layers among all the upward drawings of T with any of its vertices as the root. We also extend our results on a rooted tree to give an algorithm for an upward drawing of a rooted ordered tree. To the best of our knowledge, there is no previous algorithm for obtaining an upward drawing of a tree on the minimum number of layers.
Submitted: August 2009.
Reviewed: January 2010.
Revised: February 2010.
Accepted: March 2010.
Final: April 2010.
Published: June 2010.
Communicated by Giuseppe Liotta