Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
DOI: 10.7155/jgaa.00206 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.
|
Reviewed: January 2010. Revised: February 2010. Published: June 2010. Submitted: August 2009. Accepted: March 2010. Final: April 2010. Communicated by Giuseppe Liotta |
Journal of Graph Algorithms and Applications |