Let R and B be two disjoint sets of points in the plane such that | B| ≤ | R| , and no three points of R∪ B are collinear. We show that the geometric complete bipartite graph K(R, B) contains a non-crossing spanning tree whose maximum degree is at most max{3,⌈(|R|-1)/|B|⌉+1}; this is the best possible upper bound on the maximum degree. This proves two conjectures made by Kaneko, 1998, and solves an open problem posed by Abellanas et al. at the Graph Drawing Symposium, 1996.

, ,
Discrete and Computational Geometry
Computational Geometry Lab

Biniaz, A. (Ahmad), Bose, P, Maheshwari, A, & Smid, M. (2018). Plane Bichromatic Trees of Low Degree. Discrete and Computational Geometry, 59(4), 864–885. doi:10.1007/s00454-017-9881-z