Straight-line embeddings of two rooted trees in the plane (Q1293679): Difference between revisions

Let \(T_1\) and \(T_2\) be two disjoint rooted trees of orders \(n_1\) and \(n_2\), with roots \(v_1\) and \(v_2\). Let \(P\) be a set of \(n_1+n_2\) points in the plane in a general position, containing two specified points \(p_1\) and \(p_2\). The authors prove that the union of \(T_1\) and \(T_2\) can be straight-line embedded in the plane onto \(P\) in such a way that \(v_i\) corresponds to \(p_i\) for \(i=1,2\). Moreover, an \(O(n^2\log{n})\) time algorithm is given for finding such an embedding, where \(n=n_1+n_2\).