
Optimal Algorithms to Embed Trees
in a Point Set ?
Prosenjit Bosey Michael McAllisterz Jack Snoeyinkx
Department of Computer Science, University of British Columbia,
Vancouver, BC, V6T 1Z2
Abstract
We present optimal ?(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 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.
1 Introduction
The problem of deciding whether a set of points admits a certain combinatorial structure, as well as computing an embedding of that structure on the point set, has been a recurrent theme in many fields. The list of problems falling into this category is virtually endless. We mention a few of the structures that are current topics of research.
The triangulation of a point set is a structure that has spurred much research because of its many applications in areas such as finite element methods, graphics, medical imaging, Geographic Information Systems (GIS), statistics, scattered data interpolation, and pattern recognition, to name a few [14, 15].
The combinatorial structure of interest in this paper is the tree, which is wellstudied in the
literature. For example, the study of spanning trees of a set of points has a long history. From
a graph drawing perspective (see [5] for a survey of graph drawing), the traditional questions ask
whether a (rooted or free) tree T = (V; E) can be embedded in the plane such that some criterion is
satisfied: e.g., that the area of the resulting embedding is small [4, 9], that the symmetry present in
the tree is revealed in the embedding [11], or that T is isomorphic to the minimumweight spanning
?This paper appears in the proceedings of Graph Drawing '95 and as technical report TR9522 from the Department
of Computer Science, University of British Columbia.
yPartially supported by an NSERC and a Killam Postdoctoral Fellowship
zPartially supported by an NSERC Postgraduate Fellowship
xPartially supported by an NSERC Research Grant and a B.C. Advanced Systems Institute Fellowship.