Minimum-Layer Upward Drawings of Trees - Alam, Muhammad Jawaherul; Samee, Md. Abul Hassan; Rabbi, Mashfiqui; Rahman, Md. Saidur (Journal of Graph Algorithms and Applications, 2010)
An upward drawing of a rooted tree T is a planar straight-linedrawing of T where the vertices of T are placed on a set ofhorizontal lines, called layers, such that for each vertex uof T, no child of u is placed on a layer vertically abovethe layer on which u has been placed. In this paper we givea linear-time algorithm to obtain an upward drawing of a givenrooted tree T on the minimum number of layers. Moreover, ifthe given tree T is not rooted, we can select a vertex rof T in linear time such that an upward drawing of T rootedat r would require the minimum number of layers among allthe upward drawings of T with any of its vertices as theroot. We also extend our results on a rooted tree to give analgorithm for an upward drawing of a rooted ordered tree. To thebest of our knowledge, there is no previous algorithm forobtaining an upward drawing of a tree on the minimum numberof layers. <!---->