Plane bichromatic trees of low degree (Q1650794)

Let \(R\) and \(B\) be two disjoint set of points in the plane such that \(| B|\leq| R|\) and no three points of \(R\cup B\) are collinear. The geometric complete bipartite graph \(K(R, B)\) is the bipartite graph whose vertex set is \(R\cup B\) and whose edge set consists of all straight-line segments connecting a point in \(R\) to a point in \(B\). A bichromatic tree on \(R\cup B\) is a spanning tree of \(K(R, B)\). A plane bichromatic tree is a bichromatic tree whose edges do not intersect in their interior. It is straightforward to show that the plane bichromatic trees always exist; this paper is concerned with the problem of finding such trees with maximum degree as small as possible. By a simple degree count it is clear that \((| R|-1)/| B|+1\) is the best possible upper bound on the maximum degree. The authors show that there is always a plane chromatic tree whose maximum degree is at most \(\max \,\{3, \lceil (|R|-1)/|B|\rceil + 1\}\). This proves two conjectures made by \textit{A. Kaneko} [Lect. Notes Comput. Sci. 1763, 166--171 (2000; Zbl 0959.05033)], and solves an open problem posed by \textit{M. Abellanas} et al. [Discrete Appl. Math. 93, No. 2--3, 141--148 (1999; Zbl 0929.05021)]. Furthermore, the authors can compute the aforementioned tree in \(O(nx\mathrm{ polylog}(n))\) time.