Abstract.
We prove the following theorem: Let T 1 and T 2 be two disjoint rooted trees with roots v 1 and v 2 , respectively, and let P be a set of |T1 \(\cup\) T2| points in the plane in general position containing two specified points p 1 and p 2 . Then the union T 1 $\cup$ T 2 can be straight-line embedded onto P such that v 1 and v 2 correspond to p 1 and p 2 , respectively. Moreover, we give a O(n 2log n) time algorithm for finding such an embedding, where n is the number of vertices contained in T 1 $\cup$ T 2 .
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received July 3, 1997, and in revised form February 25, 1998.
Rights and permissions
About this article
Cite this article
Kaneko, A., Kano, M. Straight-Line Embeddings of Two Rooted Trees in the Plane. Discrete Comput Geom 21, 603–613 (1999). https://doi.org/10.1007/PL00009441
Issue Date:
DOI: https://doi.org/10.1007/PL00009441