We study a problem proposed by Hurtado et al. 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 \geq 3$ and provide a $(2 - \frac{1}{3 + 2\rho})$-approximation algorithm for $k = 3$ that runs in polynomial time, where $\rho$ 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.