Finding Geometric Trees with Fixed Bipartite Point-Sets

A geometric graph is a graph drawn in the plane such that a) no three vertices are colinear and b) edges are straight line segments. Edges are allowed to cross, but only transversally at interior points.

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

Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of VermontBurlingtonVT 05401-1455 USA (with thanks to Janos Pach)

Send comments to

December 2003