Parallel h-v Drawings of Binary Trees

. In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in O(log 2 n) parallel time by using a polynomial number of EREW processors. The method can be extended to compute optimal inclusion layouts in the case where each leaf l of the tree is represented by rectangle l x \Theta l y . Our method also yields an NC algorithm for the slicing floorplanning problem. Whether this problem was in NC was an open question [2]. 1 Introduction In this paper we examine drawings of rooted binary trees. We study the h-v drawing convention studied by Crescenzi, Di Battista and Piperno [3] and Eades, Lin and Lin [7]. Our results extend to the inclusion convention [6], and to slicing floorplanning [10, 2]. The drawing of a rooted binary tree using the h-v drawing convention is a planar grid drawing in which tree nodes are ..