Examining edge congestion

ABSTRACT

Many applications have emerged that attempt to visualize various aspects of web structure, links, and usage history. These visualizations often rely on graphs to provide a general view and reveal individual relationships. However, these relationships which are explicit in the graph structure are often not visually accessible due to edge congestion problems. In this paper we discuss edge congestion issues and present an interactive approach to handling them. Our edge-displacement algorithm temporarily adjusts the graph layout without distorting the user's mental map. Our algorithm opens up sufficient space to clarify relationship details without moving nodes at all; only edges are shifted.

REFERENCES

• 1: R. A. Becker and S. G. Eick. Graphical methods to analyze network data. In IEEE International Conference on Communications ICC'93, 946-951, 1993.
• 2: Eric A. Bier , Maureen C. Stone , Ken Fishkin , William Buxton , Thomas Baudel, A taxonomy of see-through tools, Proceedings of the SIGCHI conference on Human factors in computing systems: celebrating interdependence, p.358-364, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/191666.191786]
• 3: M. Sheelagh T. Carpendale , David J. Cowperthwaite , F. David Fracchia, Extending Distortion Viewing from 2D to 3D, IEEE Computer Graphics and Applications, v.17 n.4, p.42-51, July 1997 [doi>10.1109/38.595268]
• 4: Giuseppe Di Battista , Peter Eades , Roberto Tamassia , Ioannis G. Tollis, Algorithms for drawing graphs: an annotated bibliography, Computational Geometry: Theory and Applications, v.4 n.5, p.235-282, Oct. 1994 [doi>10.1016/0925-7721(94)00014-X]
• 5: G. W. Furnas, Generalized fisheye views, Proceedings of the SIGCHI conference on Human factors in computing systems, p.16-23, April 13-17, 1986, Boston, Massachusetts, United States
• 6: Y. K. Leung , M. D. Apperley, A review and taxonomy of distortion-oriented presentation techniques, ACM Transactions on Computer-Human Interaction (TOCHI), v.1 n.2, p.126-160, June 1994 [doi>10.1145/180171.180173]
• 7: K. Misue, P. Eades, W. Lai, and K. Sugiyama. Layout adjustment and the mental map. Journal of Visual Languages and Computing, 6(2):183-210, 1995

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human information processing

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Visual

General Terms:
Algorithms, Design, Human Factors

Keywords:
distortion viewing, graph layout, navigation, web visualization