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.

Additional Metadata
Keywords Bichromatic trees, Low-degree trees, Plane trees
Persistent URL dx.doi.org/10.1007/s00454-017-9881-z
Journal Discrete and Computational Geometry
Citation
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