Connected Matchings

We show that each set of n 2 points in the plane in general position has a straight-line matching with at least (5n+1) /27 edges whose segments form a connected set, and such a matching can be computed in O (n n) time. As an upper bound, we show that for some planar point sets in general position the largest matching whose segments form a connected set has n-13 edges. We also consider a colored version, where each edge of the matching should connect points with different colors.