Colored spanning graphs for set visualization

F. Hurtado, M. Korman, M.J. Kreveld, van, M. Löffler, V. Sacristán, R.I. Silveira, B. Speckmann

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

10 Citaten (Scopus)

Samenvatting

We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem is NP-hard. Hence we give an (½ ¿ + 1)-approximation, where ¿ is the Steiner ratio. We also present efficient exact solutions if the points are located on a line or a circle. Finally we consider extensions to more than two sets.
Originele taal-2Engels
TitelGraph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers
RedacteurenS. Wismath, A. Wolff
Plaats van productieBerlin
UitgeverijSpringer
Pagina's280-291
ISBN van geprinte versie78-3-319-03840-7
DOI's
StatusGepubliceerd - 2013
Evenement21st International Symposium on Graph Drawing (GD 2013) - Bordeaux, Frankrijk
Duur: 23 sep 201325 sep 2013
Congresnummer: 21
http://gd2013.labri.fr/

Publicatie series

NaamLecture Notes in Computer Science
Volume8242
ISSN van geprinte versie0302-9743

Congres

Congres21st International Symposium on Graph Drawing (GD 2013)
Verkorte titelGD 2013
LandFrankrijk
StadBordeaux
Periode23/09/1325/09/13
Ander21st International Symposium on Graph Drawing
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Colored spanning graphs for set visualization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit