Colored Spanning Graphs for Set Visualization

Hurtado, Ferran and Korman, Matias and van Krevelt, Marc and Löffler, Maarten and Sacristán, Vera and Silveira, Rodrigo I. and Speckmann, Bettina (2013) Colored Spanning Graphs for Set Visualization. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 280-291 (Official URL:

Full text not available from this repository.


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 (12ρ+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.

Item Type:Conference Paper
Classifications:P Styles > P.999 Others
Z Theory > Z.500 Representations
ID Code:1382

Repository Staff Only: item control page


Abellanas, M., Hurtado, F., Icking, C., Klein, R., Langetepe, E., Ma, L., Palop, B., Sacristán, V.: Smallest color-spanning objects. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 278–289. Springer, Heidelberg (2001)

Agarwal, P.K., Govindarajan, S., Muthukrishnan, S.M.: Range searching in categorical data: Colored range searching on grid. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, pp. 17–28. Springer, Heidelberg (2002)

Alper, B., Riche, N., Ramos, G., Czerwinski, M.: Design study of LineSets, a novel set visualization technique. IEEE TVCG 17(12), 2259–2267 (2011)

Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753–782 (1998)

Brandes, U., Cornelsen, S., Pampel, B., Sallaberry, A.: Path-based supports for hypergraphs. J. Discrete Algorithms 14, 248–261 (2012)

Brass, P., Moser, W.O.J., Pach, J.: Research Problems in Discrete Geometry. Springer, New York (2005)

Byelas, H., Telea, A.: Towards realism in drawing areas of interest on architecture diagrams. Visual Languages and Computing 20(2), 110–128 (2009)

Chung, F., Graham, R.: A new bound for Euclidean Steiner minimum trees. Ann. N.Y. Acad. Sci. 440, 328–346 (1986)

Collins, C., Penn, G., Carpendale, S.: Bubble Sets: Revealing set relations with isocontours over existing visualizations. IEEE TVCG 15(6), 1009–1016 (2009)

Dinkla, K., van Kreveld, M., Speckmann, B., Westenberg, M.A.: Kelp Diagrams: Point set membership visualization. Computer Graphics Forum 31(3), 875–884 (2012)

Edwards, A.W.F.: Cogwheels of the mind. John Hopkins University Press (2004)

Gilbert, E., Pollak, H.: Steiner minimal trees. SIAM J. Appl. Math. 16, 1–29 (1968)

Henry Riche, N., Dwyer, T.: Untangling Euler diagrams. IEEE TVCG 16(6), 1090–1099 (2010)

Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane – a survey. In: Discrete and Comp. Geometry, The Goodman-Pollack Festschrift, pp. 551–570 (2003)

Meulemans, W., Henry Riche, N., Speckmann, B., Alper, B., Dwyer, T.: KelpFusion: a hybrid set visualization technique. In: IEEE TVCG (to appear, 2013)

Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Handbook of Computational Geometry, pp. 633–701 (1998)

Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298–1309 (1999)

Mount, D.M., Netanyahu, N.S., Silverman, R., Wu, A.Y.: Chromatic nearest neighbor searching: A query sensitive approach. Computational Geometry: Theory and Applications 17(3-4), 97–119 (2000)

Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, New York (1985)

Simonetto, P., Auber, D.: Visualise undrawable Euler diagrams. In: Proc. 12th Conf. on Information Visualisation, pp. 594–599 (2008)

Stapleton, G., Rodgers, P., Howse, J., Zhang, L.: Inductively generating Euler diagrams. IEEE TVCG 17(1), 88–100 (2011)

Tokunaga, S.: Intersection number of two connected geometric graphs. Information Processing Letters 59(6), 331–333 (1996)

Tufte, E.R.: The Visual Display of Quantitative Information. Graphics Press (1983)