BIB-VERSION:: CS-TR-v2.0
ID:: ncstrl.dartmouthcs//TR93-202
ENTRY:: January 20, 1995
ORGANIZATION:: Dartmouth College, Computer Science
TITLE:: Parallel h-v Drawings of Binary Trees
TYPE:: Technical Report (paper)
REVISION:: 1
AUTHOR:: Metaxas, Panagiotis
AUTHOR:: Pantziou, Grammati E.
AUTHOR:: Symvonis, Antonios
NOTE:: The 'January' in DATE is an arbitrary placeholder.
DATE:: January 1993
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(\log^2 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 $l_x
\times l_y$ (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~\cite{CT90}.
RETRIEVAL:: For a paper copy, email <reports@cs.dartmouth.edu>
RETRIEVAL:: For a paper copy, write to
       Technical Report Librarian
       Department of Computer Science
       Dartmouth College
       6211 Sudikoff Laboratory
       Hanover, NH 03755-3510
       USA
RETRIEVAL:: PDF at http://www.cs.dartmouth.edu/reports/TR93-202.pdf
END::