Drawing a tree on parallel lines

✍ Scribed by R. Hirabayashi; Y.T. Ikebe; K. Iwamura; T. Nakayama

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 336 KB
• Volume: 37
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(99)00155-8

✦ Synopsis

We consider a problem of drawing a tree on parallel lines. In this problem we are given a tree and an infinite number of parallel lines in the plane. The object is to draw the tree so that (i) each vertex is placed on one of the given parallel lines, (ii) no two edges intersect, and (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 wtlich solves it recursively. (~) 1999 Elsevier Science Ltd. All rights reserved.