Drawing Clustered Graphs as Topographic Maps

Gronemann, Martin and Jünger, Michael (2013) Drawing Clustered Graphs as Topographic Maps. In: 20th International Symposium, GD 2012, September 19-21, 2012, Redmond, WA, USA , pp. 426-438 (Official URL: http://link.springer.com/chapter/10.1007/978-3-642-36763-2_38).

Full text not available from this repository.


The visualization of clustered graphs is an essential tool for the analysis of networks, in particular, social networks, in which clustering techniques like community detection can reveal various structural properties. In this paper, we show how clustered graphs can be drawn as topographic maps, a type of map easily understandable by users not familiar with information visualization. Elevation levels of connected entities correspond to the nested structure of the cluster hierarchy. We present methods for initial node placement and describe a tree mapping based algorithm that produces an area efficient layout. Given this layout, a triangular irregular mesh is generated that is used to extract the elevation data for rendering the map. In addition, the mesh enables the routing of edges based on the topographic features of the map.

Item Type:Conference Paper
Additional Information:10.1007/978-3-642-36763-2_38
Classifications:G Algorithms and Complexity > G.350 Clusters
P Styles > P.180 Cluster
P Styles > P.300 Curved
S Software and Systems > S.120 Visualization
ID Code:1330

Repository Staff Only: item control page


Balzer, M., Deussen, O.: Level-of-detail visualization of clustered graph layouts. In: Asia-Pacific Symposium on Visualization, pp. 133–140 (2007)

Balzer, M., Deussen, O., Lewerentz, C.: Voronoi treemaps for the visualization of software metrics. In: Proceedings of the 2005 ACM Symposium on Software Visualization, pp. 165–172 (2005)

De Berg, M., Onak, K., Sidiropoulos, A.: Fat polygonal partitions with applications to visualization and embeddings. CoRR abs/1009.1866 (2010)

de Berg, M., Speckmann, B., van der Weele, V.: Treemaps with Bounded Aspect Ratio. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 260–270. Springer, Heidelberg (2011)

Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Social Networks 30(2), 136–145 (2008)

CGAL - Computational Geometry Algorithms Library, http://www.cgal.org/

Cortese, P.F., Battista, G.D., Moneta, A., Patrignani, M., Pizzonia, M.: Topographic visualization of prefix propagation in the internet. IEEE Trans. Vis. Comput. Graph. 12(5), 725–732 (2006)

Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall (1999)

Fabrikant, S.I., Montello, D.R., Mark, D.M.: The natural landscape metaphor in information visualization: The role of commonsense geomorphology. J. Am. Soc. Inf. Sci. Technol. 61(2), 253–270 (2010)

Gansner, E.R., Hu, Y., Kobourov, S.G.: GMap: Visualizing graphs and clusters as maps. In: PacificVis, pp. 201–208. IEEE (2010)

Garland, M., Kumar, G.: Visual exploration of complex time-varying graphs. IEEE Transactions on Visualization and Computer Graphics 12, 805–812 (2006)

GDAL - Geospatial Data Abstraction Library, http://gdal.org/

GDEA - Graph Drawing E-Print Archive, http://gdea.informatik.uni-koeln.de/

Girvan, M., Newman, M.E.J.: Community structure in social and biological networks. Proceedings of the National Academy of Sciences 99, 7821–7826 (2002)

Gronemann, M., Jünger, M., Kriege, N., Mutzel, P.: MolMap: Visualizing molecule libraries as topographic maps. Tech. rep (2012)

Holten, D.: Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and Computer Graphics 12(5), 741–748 (2006)

Johnson, B., Shneiderman, B.: Tree-maps: a space-filling approach to the visualization of hierarchical information structures. In: Proceedings of the 2nd Conference on Visualization 1991, pp. 284–291 (1991)

Lambert, A., Bourqui, R., Auber, D.: Winding roads: Routing edges into bundles. Computer Graphics Forum 29(3), 853–862 (2010)

Mapnik, http://mapnik.org/

Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74, 036104 (2006)

OGDF - Open Graph Drawing Framework, http://www.ogdf.net/

Wise, J., Thomas, J., Pennock, K., Lantrip, D., Pottier, M., Schur, A., Crow, V.: Visualizing the non-visual: Spatial analysis and interaction with information from text documents. IEEE Trans. Vis. Comput. Graph., 51–58 (1995)