**O. Aichholzer, F. Aurenhammer, T. Hackl, and C. Huemer**

We study the following Ramsey-type problem. Let be a
two-colored set of points in the plane. We show how to construct, in
time, a crossing-free spanning tree for , and
a crossing-free spanning tree for , such that both the number of
crossings between and and the diameters of and
are kept small. The algorithm is conceptually simple and is implementable
without using any non-trivial data structure. This improves over a previous
method in Tokunaga [#!T!#] that is less efficient in implementation and does
not guarantee a diameter bound.