Encompassing Colored Crossing-Free Geometric Graphs
Ferrán Hurtado, Mikio Kanō, David D. Rappaport, Csaba D. Tóth · 2004
Given n red and n blue points in the plane and a planar straight line matching between the red and the blue points, the matching can be extended into a bipartite planar straight line spanning tree. That is, any red-blue planar matching can be completed into a crossing-free red-blue spanning tree. Such a tree can be constructed in O(n log n) time.