@inproceedings{fd4b7d6bff164571a1d0c45ecaf6eaf2,
title = "Multi-Colored Spanning Graphs",
abstract = "We 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 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≥3k≥3 and provide a (2−13+2ϱ)(2−13+2ϱ) -approximation algorithm for k=3k=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.",
keywords = "COMPUTATIONAL GEOMETRY, GRAPH DRAWING, GRAPHS THEORY",
author = "Hugo Akatya and Maarten L{\"o}ffler and Csaba T{\'o}th",
year = "2016",
doi = "10.1007/978-3-319-50106-2_7",
language = "English",
isbn = "978-3-319-50105-5",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "81--93",
booktitle = "Graph Drawing and Network Visualization",
}