A

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.

**References:**

[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 *dan.archdeacon@uvm.edu*

December 2003