1997-12-01

# Optimal algorithms to embed trees in a point set

## Publication

### Publication

*
Journal of Graph Algorithms and Applications
,
Volume 1
p. 1-
15
*

We present optimal Θ(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 must not have crossing edges.

Additional Metadata | |
---|---|

Journal of Graph Algorithms and Applications | |

Organisation | School of Computer Science |

Bose, P, McAllister, M. (Michael), & Snoeyink, J. (Jack). (1997). Optimal algorithms to embed trees in a point set.
Journal of Graph Algorithms and Applications, 1, 1–15. |