MapSets: Visualizing Embedded and Clustered Graphs

Efrat, Alon and Hu, Yifan and Kobourov, Stephen G. and Pupyrev, Sergey (2014) MapSets: Visualizing Embedded and Clustered Graphs. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 452-463 (Official URL:

Full text not available from this repository.


We describe MapSets, a method for visualizing embedded and clustered graphs. The proposed method relies on a theoretically sound geometric algorithm, which guarantees the contiguity and disjointness of the regions representing the clusters, and also optimizes the convexity of the regions. A fully functional implementation is available online and is used in a comparison with related earlier methods.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_38
Classifications:G Algorithms and Complexity > G.350 Clusters
G Algorithms and Complexity > G.560 Geometry
M Methods > M.400 Force-directed / Energy-based
M Methods > M.900 Tree
P Styles > P.180 Cluster
P Styles > P.999 Others
ID Code:1454

Repository Staff Only: item control page


Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E. (1991) Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Comput. Geom. 6: pp. 407-422

Alper, B., Riche, N.H., Ramos, G., Czerwinski, M. (2011) Design study of LineSets, a novel set visualization technique. IEEE Trans. Vis. Comput. Graphics 17: pp. 2259-2267

Arora, S., Chang, K. (2004) Approximation schemes for degree-restricted MST and red–blue separation problems. Algorithmica 40: pp. 189-210

Boyack, K.W., Klavans, R., Börner, K. (2005) Mapping the backbone of science. Scientometrics 64: pp. 351-374

Chung, F., Graham, R. (1985) A new bound for Euclidean Steiner minimal trees. Annals of the New York Academy of Sciences 440: pp. 328-346

Collins, C., Penn, G., Carpendale, S. (2009) Bubble sets: Revealing set relations with isocontours over existing visualizations. IEEE Trans. Vis. Comput. Graphics 15: pp. 1009-1016

Dinkla, K., Kreveld, M.J., Speckmann, B., Westenberg, M.A. (2012) Kelp diagrams: Point set membership visualization. Comput. Graph. Forum 31: pp. 875-884

Dwyer, T., Nachmanson, L. Fast edge-routing for large graphs. In: Eppstein, D., Gansner, E.R. eds. (2010) Graph Drawing. Springer, Heidelberg, pp. 147-158

Hu, Y., Gansner, E.R., Kobourov, S.G. (2010) Visualizing graphs and clusters as maps. IEEE Comput. Graphics and Appl. 30: pp. 54-66

Hurtado, F., Korman, M., Kreveld, M., Löffler, M., Sacristán, V., Silveira, R.I., Speckmann, B. Colored spanning graphs for set visualization. In: Wismath, S., Wolff, A. eds. (2013) Graph Drawing. Springer, Heidelberg, pp. 280-291

Jianu, R., Rusu, A., Hu, Y., Taggart, D. (2014) How to display group information on node-link diagrams: An evaluation. IEEE Trans. Vis. Comput. Graphics 20: pp. 1530-1541

Kanizsa, G., Gerbino, W.: Convexity and symmetry in figure-ground organization. Vision and Artifact, 25–32 (1976)

Kobourov, S.G., Pupyrev, S., Simonetto, P.: Visualizing graphs as maps with contiguous regions. Comput. Graph. Forum (2014)

Kratochvíl, J., Nešetřil, J. (1990) Independent set and clique problems in intersection-defined classes of graphs. Commentationes Math. Univ. Carolinae 31: pp. 85-93

Meulemans, W., Riche, N., Speckmann, B., Alper, B., Dwyer, T. (2013) KelpFusion: A hybrid set visualization technique. IEEE Trans. Vis. Comput. Graphics 19: pp. 1846-1858

Mitchell, J.S. (2000) Geometric shortest paths and network optimization. Handbook of Computational Geometry 334: pp. 633-702

Novembre, et al.: Genes mirror geography within Europe. Nature 456(7218), 98–101 (2008)

Pupyrev, S., Nachmanson, L., Bereg, S., Holroyd, A.E. Edge routing with ordered bundles. In: Kreveld, M., Speckmann, B. eds. (2011) GD 2011. Springer, Heidelberg, pp. 136-147

Purves, D., Lotto, R.B.: Why we see what we do: An empirical theory of vision. Sinauer Associates (2003)

Riche, N.H., Dwyer, T. (2010) Untangling Euler diagrams. IEEE Trans. Vis. Comput. Graphics 16: pp. 1090-1099

Simonetto, P., Auber, D., Archambault, D. (2009) Fully automatic visualisation of overlapping sets. Comput. Graph. Forum 28: pp. 967-974

Skupin, A., Fabrikant, S.I. (2003) Spatialization methods: a cartographic research agenda for non-geographic information visualization. Cartogr. Geogr. Inform. 30: pp. 95-119

Sonka, M., Hlavac, V., Boyle, R.: Image Processing, Analysis, and Machine Vision. Thomson-Engineering (2007)

Zunic, J., Rosin, P.L. (2002) A convexity measurement for polygons. IEEE Trans. Pattern Anal. Mach. Intell. 26: pp. 173-182