Drawing Clustered Graphs as Topographic Maps

Gronemann, Martin and Jünger, Michael Drawing Clustered Graphs as Topographic Maps. [Preprint]

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
17Mb

Abstract

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 visu- alization. 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 ir- regular 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 topo- graphic features of the map.

Item Type:Preprint
Classifications:G Algorithms and Complexity > G.350 Clusters
M Methods > M.900 Tree
P Styles > P.300 Curved
S Software and Systems > S.120 Visualization
ID Code:1288

Repository Staff Only: item control page

References

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: Proceedings of the 22nd International Symposium on Algorithms and Computation. pp. 260–270 (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)

Dwyer, T., Nachmanson, L.: Fast edge-routing for large graphs. In: Proceedings of the 17th International Symposium on Graph Drawing. pp. 147–158 (2010).

Eades, P.: A heuristic for graph drawing. Congressus Numerantium 42, 149–160 (1984)

Fruchterman, T.M.J., Reingold, E.M.: Graph drawing by force-directed placement. Softw. Pract. Exper. 21(11), 1129–1164 (1991)

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 (2012), submitted to GD 2012

Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Proceedings of the 12th International Symposium on Graph Drawing. pp. 285–295 (2004)

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 ’91. pp. 284–291 (1991)

Kohonen, T.: Self-Organizing Maps. Springer (2000)

Kuhn, A., Loretan, P., Nierstrasz, O.: Consistent layout for thematic software maps. In: Proceedings of the 2008 15th Working Conference on Reverse Engineering. pp. 209–218 (2008)

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/

Qu, H., Zhou, H., Wu, Y.: Controllable and progressive edge clustering for large networks. In: Proceedings of the 14th International Symposium on Graph Drawing. pp. 399–404 (2007)