ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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 2 log n) time algorithm for finding such an embedding, where n is the number of vertices contained in T 1 $\cup$ T 2 .
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009441
Permalink