Multicolored Spanning GraphsAkitaya, Hugo A. and Löffler, Maarten and Tóth, Csaba D. (2016) Multicolored Spanning Graphs. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 8193(Official URL: http://dx.doi.org/10.1007/9783319501062_7). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_7
AbstractWe study a problem proposed by Hurtado et al. [10] 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 MinCSG problem asks for the minimum sum of edge lengths in a colored spanning graph. We show that the problem is NPhard for k primary colors when k≥3 and provide a (2−1/(3+2ϱ))approximation algorithm for k=3 that runs in polynomial time, where ϱ 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.
Actions (login required)
