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

doi:10.1007/978-3-319-03841-4_25

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

12 Citations (Scopus)

4 Downloads (Pure)

Abstract

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.

Original language	English
Title of host publication	Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers
Editors	S. Wismath, A. Wolff
Place of Publication	Berlin
Publisher	Springer
Pages	280-291
ISBN (Print)	78-3-319-03840-7
DOIs	https://doi.org/10.1007/978-3-319-03841-4_25
Publication status	Published - 2013
Event	21st International Symposium on Graph Drawing (GD 2013) - Bordeaux, France Duration: 23 Sept 2013 → 25 Sept 2013 Conference number: 21 http://gd2013.labri.fr/

Publication series

Name	Lecture Notes in Computer Science
Volume	8242
ISSN (Print)	0302-9743

Conference

Conference	21st International Symposium on Graph Drawing (GD 2013)
Abbreviated title	GD 2013
Country/Territory	France
City	Bordeaux
Period	23/09/13 → 25/09/13
Other	21st International Symposium on Graph Drawing
Internet address	http://gd2013.labri.fr/

Access to Document

10.1007/978-3-319-03841-4_25

Cite this

Hurtado, F., Korman, M., Kreveld, van, M. J., Löffler, M., Sacristán, V., Silveira, R. I., & Speckmann, B. (2013). Colored spanning graphs for set visualization. In S. Wismath, & A. Wolff (Eds.), Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers (pp. 280-291). (Lecture Notes in Computer Science; Vol. 8242). Springer. https://doi.org/10.1007/978-3-319-03841-4_25

@inproceedings{72ca23c60c364312a7a71fd618189f0f,

title = "Colored spanning graphs for set visualization",

abstract = "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.",

author = "F. Hurtado and M. Korman and \{Kreveld, van\}, M.J. and M. L{\"o}ffler and V. Sacrist{\'a}n and R.I. Silveira and B. Speckmann",

year = "2013",

doi = "10.1007/978-3-319-03841-4\_25",

language = "English",

isbn = "78-3-319-03840-7",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "280--291",

editor = "S. Wismath and A. Wolff",

booktitle = "Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers",

address = "Germany",

note = "21st International Symposium on Graph Drawing (GD 2013), GD 2013 ; Conference date: 23-09-2013 Through 25-09-2013",

url = "http://gd2013.labri.fr/",

}

Hurtado, F, Korman, M, Kreveld, van, MJ, Löffler, M, Sacristán, V, Silveira, RI & Speckmann, B 2013, Colored spanning graphs for set visualization. in S Wismath & A Wolff (eds), Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8242, Springer, Berlin, pp. 280-291, 21st International Symposium on Graph Drawing (GD 2013), Bordeaux, France, 23/09/13. https://doi.org/10.1007/978-3-319-03841-4_25

Colored spanning graphs for set visualization. / Hurtado, F.; Korman, M.; Kreveld, van, M.J. et al.
Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers. ed. / S. Wismath; A. Wolff. Berlin: Springer, 2013. p. 280-291 (Lecture Notes in Computer Science; Vol. 8242).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Colored spanning graphs for set visualization

AU - Hurtado, F.

AU - Korman, M.

AU - Kreveld, van, M.J.

AU - Löffler, M.

AU - Sacristán, V.

AU - Silveira, R.I.

AU - Speckmann, B.

N1 - Conference code: 21

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-03841-4_25

DO - 10.1007/978-3-319-03841-4_25

M3 - Conference contribution

SN - 78-3-319-03840-7

T3 - Lecture Notes in Computer Science

SP - 280

EP - 291

BT - Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers

A2 - Wismath, S.

A2 - Wolff, A.

PB - Springer

CY - Berlin

T2 - 21st International Symposium on Graph Drawing (GD 2013)

Y2 - 23 September 2013 through 25 September 2013

ER -

Hurtado F, Korman M, Kreveld, van MJ, Löffler M, Sacristán V, Silveira RI et al. Colored spanning graphs for set visualization. In Wismath S, Wolff A, editors, Graph Drawing : 21st International Symposium, GD 2013, Bordeaux, France, September 23-25, 2013, Revised Selected Papers. Berlin: Springer. 2013. p. 280-291. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-03841-4_25

Colored spanning graphs for set visualization

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this