Increasing the readability of graph drawings with centrality-based scaling

ABSTRACT

A common problem in visualising some networks is the presence of localised high density areas in an otherwise sparse graph. Applying common graph drawing algorithms on such networks can result in drawings that are not highly readable in the dense areas. Additionally, networks whose layouts are defined geographically often have dense areas that are located within small geographical regions relative to the size of the entire network. In cases where relationships within these dense areas are of interest, it is desirable to be able to distort the graph layout such that the denser areas are enlarged from their original sizes.In this paper, we propose a technique for enlarging dense areas of a given graph layout, and shrinking sparse areas. This technique is applied to geographical layouts of railway networks and force-directed layouts of non-geographical networks. The results show an increase in readability of dense parts of the networks. In addition, they provide improved starting layouts for schematisation methods which may be used to further increase readability.

REFERENCES

• 1: Ahmed, A., Dwyer, T., Forster, M., Fu, X., Ho, J., Hong, S.-H., Koschützki, D., Murray, C., Nikolov, N. S., Taib, R., Tarassov, A. & Xu, K. (2005), GEOMI: GEOmetry for Maximum Insight, to appear in Proc. of the 13th International Symposium on Graph Drawing.
• 2: Anthonisse, J. M. (2005), The rush in a directed graph, Technical Report BN 9/71, Stichting Mathetmatisch Centrum, Amsterdam.
• 3: Boisvert, R. F., Hicklin, J., Miller, B., Moler, C., Pozo, R., Remington, K. & Webb, P. (2005), JAMA: Java Matrix Package, Accessed on 7th October 2005 at http://math.nist.gov/javanumerics/jama/.
• 4: Bonacich, P. (1987), Power and centrality: a family of measures, American Journal of Sociology, 92:1170-1182.
• 5: Brandes, U. (2001), A faster algorithm for betweenness centrality, Journal of Mathematical Sociology, 25(2):163-177.
• 6: Sergio Cabello , Mark de Berg , Marc van Kreveld, Schematization of networks, Computational Geometry: Theory and Applications, v.30 n.3, p.223-238, March 2005 [doi>10.1016/j.comgeo.2004.11.002]
• 7: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 8: Eades, P. (1984), A heuristic for graph drawing, Congressus Numerantium, 42:149-160.
• 9: Freeman, L. (1977), A set of measures of centrality based on betweenness, Sociometry, 40:35-41.
• 10: Friedrich, C. (2002), Animation in relational information visualisation, PhD Thesis, University of Sydney, Sydney, Australia, 2002.
• 11: Garland, K. (1994), Mr. Beck's Underground Map, Capital Transport Publishing, England.
• 12: Ivan Herman , Guy Melançon , M. Scott Marshall, Graph Visualization and Navigation in Information Visualization: A Survey, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.24-43, January 2000 [doi>10.1109/2945.841119 ]
• 13: Hong, S.-H., Merrick, D. & do Nascimento, H. A. D. (2005), The metro map layout problem, In Proc. of the 12th International Symposium on Graph Drawing, p. 482-491.
• 14: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 15: Lyons, K. A., Meijer, H. & Rappaport, D. (1998), Algorithms for cluster busting in anchored graph drawing, Journal of Graph Algorithms and Applications, 2(1):1-24.
• 16: Merrick, D. & Gudmundsson, J. (2005), C-Directed Path Simplication for Metro Map Layout, Manuscript.
• 17: Gabriele Neyer, Line Simplification with Restricted Orientations, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.13-24, August 11-14, 1999
• 18: Nöllenburg, M. & Wolff, A. (2005), A mixed-integer program for drawing high-quality metro maps. To appear in Proc. of the 13th International Symposium on Graph Drawing.
• 19: O'Madadhain, J., Fisher, D., Smyth, P., White, S. & Boey, Y.-B. (2005), Analysis and visualization of network data using JUNG, To appear in Journal of Statistical Software. Accessed on 7th October 2005 at http://jung.sourceforge.net/ .
• 20: Shimizu E. & Inoue, R. (2003), Time-distance mapping: visualization of transportation level of service, In Proc. of Symposium on Environmental Issues Related to Infrastructure Development, p. 221-230.
• 21: Jonathan M. Stott , Peter Rodgers, Metro Map Layout Using Multicriteria Optimization, Proceedings of the Information Visualisation, Eighth International Conference on (IV'04), p.355-362, July 14-16, 2004 [doi>10.1109/IV.2004.94]
• 22: Tufte, E. R. (1997), Visual Explanations, Graphics Press, Cheshire.
• 23: Wasserman, S. & Faust, K. (1994), Social Network Analysis: Methods and Applications, Cambridge University Press.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems
      I.3.6 Methodology and Techniques
          Subjects: Interaction techniques

General Terms:
Algorithms, Design

Keywords:
centrality, graph drawing, metro maps