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: 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.

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 well-studied 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 minimum-weight spanning ?This paper appears in the proceedings of Graph Drawing '95 and as technical report TR-95-22 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.