Parallel h-v drawings of binary trees - Panagiotis T. Metaxas; Grammati E. Pantziou; Antonis Symvonis (ISAAC'94: Proceedings of the International Symposium on Algorithms and Computations, 1994)
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(log2n) 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*l y. Our method also yields an NC algorithm for the slicing floorplanning problem. Whether this problem was in NC was an open question.