Drawing a tree on parallel lines

AbstractWe consider a problem of drawing a tree on parallel lines. In this problem we given a tree and an infinite number of parallel lines in the plane. The object is to draw the tree so that 1.(i) each vertex is placed on one of the given parallel lines,2.(ii) no two edges intersect, and3.(iii) the ‘height’ of each vertex is nondecreasing, while minimizing the total number of lines used. We show that this problem is solvable in time linear on the size of the tree, by presenting an algorithm which solves it recursively