Suppose that we are given point sets P_1 and P_2 in the plane with |P_1| at least |P_2|.
Problem: Is there a constant c such that there always exist a crossing-free geometric tree on P_1 union P_2 where every edge joins a vertex in P_1 to one in P_2 and with every vertex of degree at most c|P_1|/|P_2|?
Abellanas et al. have shown that there is such a tree if a) every vertex is on the boundary of the convex hull of P_1 union P_2, or b) there is a line with P_1 on one side and P_2 on the other.
[A] M. Abellanas, J. Garcia, G. Hernandez, M. Noy, and P. Ramos, Bipartite
embeddings of trees in the plane, in Graph Drawing '96 (Ed. S. North),
Lecture Notes in Computer Science, 1190, Springer-Verlag,
Berlin (1997) 1-10
Send comments to email@example.com