Optimal tree layout (Preliminary Version)
Michael J. Fischer, Michael Stewart Paterson · 1980
We consider the problem of finding a minimal cost layout of a tree in Euclidian d-space. A tree is an acyclic undirected edge-weighted graph, and a layout is an assignment of a point in d-dimensional Euclidian space to each of the nodes of the tree. The “length” of an edge in the layout is the “distance” between its endpoints as measured by some norm. The cost of an edge is its length times its weight, and the cost of the whole layout is the sum of the costs of all the edges. We assume the positions of certain nodes are fixed in advance, and we wish to place the remaining nodes so as to minimize the cost of the layout.