Drawing a tree on parallel lines (Q1963053)

The authors consider the problem of drawing a tree on parallel lines. It is assumed that the tree vertices are placed on the lines, no edges intersect (except possibly at their endpoints), and the distance from the bottom line of any vertex is nondecreasing along any path starting at a vertex on the bottom line. An optimal linear-time algorithm is proposed.