2016/08/25 by Hugo A. Akitaya, Akitaya, Hugo A., Maarten Löffler +3
Computer Science · #Computational Geometry (cs.CG) #FOS: Computer and information sciences #cs.CG
paper · pdf · doi:10.48550/arxiv.1608.07056
Appears in the Proceedings of the 24th International Symposium on Graph Drawing and Network Visualization (GD 2016)
arxiv created 2016/08/25 · arxiv updated 2016/08/26
We study a problem proposed by Hurtado et al. (2016) motivated by sparse set visualization. Given n points in the plane, each labeled with one or more primary colors, a colored spanning graph (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The Min-CSG problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NP-hard for k primary colors when k≥ 3 and provide a (2-(1)/(3+2\varrho))-approximation algorithm for k=3 that runs in polynomial time, where \varrho is the Steiner ratio. Further, we give a O(n) time algorithm in the special case that the input points are collinear and k is constant.