Bi-Chromatic Minimum Spanning Trees
Magdalene Grantson, Henk Meijer, David D. Rappaport · 2005
Let G be a set of disjoint bi-chromatic straight line segments and H be a set of red and blue points in the plane, no three points are collinear. We give tight upper bounds on the maximum degree of a node in the color conforming minimum weight spanning tree (MST) formed by G and H. We also consider bounds on the total length of the edges of 1) the planar MST and the unrestricted MST, 2) the greedy planar spanning tree and the unrestricted MST, 3) the greedy planar spanning tree and the planar MST.