Bipartite embeddings of trees in the plane

In this paper we consider the following embedding problem. A point set P in the plane in general position is partitioned into two disjoint sets R and B, and we are asked to embed a tree T in P without crossings and with the a dditional property that all the edges connect a point in R to another point in B. We study several problems related to such bipartite embeddings. (C) 1999 Elsevier Science B.V. All rights reserved.