Multi-colored spanning graphs

DOI10.1007/978-3-319-50106-2_7zbMATH Open1451.68197arXiv1608.07056OpenAlexW3023791901MaRDI QIDQ784473FDOQ784473

Authors: Hugo A. Akitaya, Maarten Löffler, Csaba D. Tóth 

Publication date: 3 August 2020

Published in: Theoretical Computer Science, Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: 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 emph{colored spanning graph} (CSG) is a graph such that for each primary color, the vertices of that color induce a connected subgraph. The extsc{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 $kge3$ and provide a $(2-frac13+2varrho)$-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.

Full work available at URL: https://arxiv.org/abs/1608.07056

Recommendations

• Multi-colored spanning graphs
• Colored spanning graphs for set visualization
• Colored spanning graphs for set visualization
• On some geometric problems of color-spanning sets
• NP-Completeness of Spreading Colored Points

zbMATH Keywords

minimum spanning treegeometric graphset visualization

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Geometric Spanner Networks
• The Problem of Compatible Representatives
• Steiner Minimal Trees
• On sparse spanners of weighted graphs
• Improved bounds on Bell numbers and on moments of sums of random variables
• On some geometric problems of color-spanning sets
• Subdivision Drawings of Hypergraphs
• Hypergraph planarity and the complexity of drawing venn diagrams
• Path-based supports for hypergraphs
• Optimal binary space partitions for segments in the plane
• On multiaspect graphs
• Colored spanning graphs for set visualization
• Spanning trees in multipartite geometric graphs
• Colored Spanning Graphs for Set Visualization
• New and improved spanning ratios for Yao graphs
• Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem
• Minimum Tree Supports for Hypergraphs and Low-Concurrency Euler Diagrams
• Title not available (Why is that?)
• Tverberg’s theorem is 50 years old: A survey
• Short Plane Supports for Spatial Hypergraphs
• Multi-colored spanning graphs

Cited In (7)

• Short plane supports for spatial hypergraphs
• Faster Algorithms for the Minimum Red-Blue-Purple Spanning Graph Problem
• On the double total dominator chromatic number of graphs
• Minimum consistent subset of simple graph classes
• Short Plane Supports for Spatial Hypergraphs
• Multi-colored spanning graphs
• The Painter’s Problem: Covering a Grid with Colored Connected Polygons

Uses Software

• eulerAPE

This page was built for publication: Multi-colored spanning graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q784473)