Optimal Algorithms to Embed Trees in a Point SetBose, Prosenjit and McAllister, Michael and Snoeyink, Jack (1996) Optimal Algorithms to Embed Trees in a Point Set. In: Symposium on Graph Drawing, GD 1995, September 2022, 1995 , pp. 6475(Official URL: http://dx.doi.org/10.1007/BFb0021791). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BFb0021791
AbstractWe present optimal \Theta(n log n) time algorithms to solve two tree embedding problems whose solution previously took quadratic time or more: rootedtree embeddings and degreeconstrained embeddings. In the rootedtree embedding problem we are given a rootedtree T with n nodes and a set of n points P with one designated point p and are asked to find a straightline embedding of T into P with the root at point p. In the degreeconstrained embedding problem we are given a set of n points P where each point is assigned a positive degree and the degrees sum to 2n2 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.
Actions (login required)
