Plane bichromatic trees of low degree
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 [Formula presented]; this is the best possible upper bound on the maximum degree.This solves an open problem posed by Abellanas et al.at the Graph Drawing Symposium, 1996.
Biniaz, A. (Ahmad), Bose, P, Maheshwari, A, & Smid, M. (2016). Plane bichromatic trees of low degree. doi:10.1007/978-3-319-44543-46