Proceedings of the 5th International Symposium, ISAAC '94
(EN)
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(log2 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×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].
(EN)
