Non-crossing geometric spanning trees with bounded degree and monochromatic leaves on bicolored point sets

Abstract

Let $R$ and $B$ be a set of red points and a set of blue points in the plane, respectively, such that $R\cup B$ is in general position, and let $f:R\to \{2,3,4,\dots \}$ be a function. We show that if $2\le |B|\le {\sum }_{x\in R}(f(x)-2)+2$, then there exists a non-crossing geometric spanning tree $T$ on $R\cup B$ such that $2\le {\mathrm{deg}}_T(x)\le f(x)$ for every $x\in R$ and the set of leaves of $T$ is $B$, where every edge of $T$ is a straight-line segment.

6 pages, 2 figures