Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00206
Minimum-Layer Upward Drawings of Trees
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
|
Journal Supporters
|