| Title: |
Multi-Colored Spanning Graphs |
| Authors: |
Akatya, Hugo; Löffler, Maarten; Tóth, Csaba; Sub Computational Geometry; Computational Geometry |
| Publication Year: |
2016 |
| Subject Terms: |
COMPUTATIONAL GEOMETRY; GRAPH DRAWING; GRAPHS THEORY; Taverne |
| Description: |
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. |
| Document Type: |
book part |
| File Description: |
text/plain |
| Language: |
English |
| Relation: |
https://dspace.library.uu.nl/handle/1874/350863 |
| Availability: |
https://dspace.library.uu.nl/handle/1874/350863 |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.2DEC742E |
| Database: |
BASE |