- View PDF version of TR-95-22 (238082 bytes)
- View PostScript version of TR-95-22
- Save PostScript version of TR-95-22
- Save gzipped PostScript version of TR-95-22 (234997 bytes)

- Optimal Algorithms to Embed Trees in a Point Set, October 1995 Prosenjit Bose, Michael McAllister and Jack Snoeyink, 11 pages
We present optimal Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rooted-tree embeddings and degree-constrained embeddings. In the rooted-tree embedding problem we are given a rooted-tree T with n nodes and a set of n points P with one designated point p and are asked to find a straight-line embedding of T into P with the root at point p. In the degree-constrained embedding problem we are given a set of n points P where each point is assigned a positive degree and the degrees sum to 2n-2 and are asked to embed a tree in P using straight lines that respects the degrees assigned to each point of P. In both problems, the points of P must be in general position and the embeddings have no crossing edges.

If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.