Parallel h-v Drawings of Binary Trees?

Panagiotis T. Metaxas 1 Grammati E. Pantziou 2

Antonis Symvonis 3

Technical Report 480
March 9, 1994

(1) Department of Computer Science, Wellesley College, Wellesley MA 02181, USA (2) Department of Mathematics and Computer Science, Dartmouth College, Hanover NH 03755, USA
(3) Department of Computer Science, University of Sydney, N.S.W. 2006, Australia

Abstract

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 number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf l of the tree is represented by rectangle lx ? ly (the dimensions of which are part of the input). For polynomial area layouts, our work places the problem of obtaining optimal size h-v or inclusion drawings in NC, presenting the first algorithm with polylogarithmic time complexity. Our method also yields an NC algorithm for the slicing floorplanning problem. Whether this problems was in NC was an open question [2].

1 Introduction

Drawing trees in a way that facilitates the understanding of the properties of the object being drawn is part of extensive research in the areas of visualization, computational geometry and documentation systems. In particular, rooted trees have been used to represent family trees, hierarchical structures and search trees.

In this paper we examine drawings of rooted binary trees. We study the h-v drawing convention studied by Eades, Lin and Lin [7] and Crescenzi, Di Battista and Piperno [3]. Our results extend to the inclusion convention [6], and to slicing floorplanning [9, 2].

?The work of the second author is partially supported by the EEC ESPRIT Basic Reasearch Action No. 7141 (ALCOM II) and by the NSF postdoctoral fellowship No. CDA-9211155. Email: [email protected], [email protected], [email protected]