The layout problem for trees with weighted edges is motivated by the design
of very-large-scale integrated circuits. Some of the nodes are fixed and t
he object is to position the remainder so that the total weighted edge cost
is minimized. The cost of each edge is the product of its weight and its l
ength under some appropriate norm. Optimization for planar layouts is shown
to be NP-hard. If crossings are permitted, then optimal layouts under the
L-1 norm can be efficiently computed. Suitable algorithms and data structur
es are presented, and explicit exact cost functions are given for two class
es of weighted complete binary trees. (C) 1999 Elsevier Science B.V. All ri
ghts reserved.