Visualizing graphs in three dimensions

ABSTRACT

It has been known for some time that larger graphs can be interpreted if laid out in 3D and displayed with stereo and/or motion depth cues to support spatial perception. However, prior studies were carried out using displays that provided a level of detail far short of what the human visual system is capable of resolving. Therefore, we undertook a graph comprehension study using a very high resolution stereoscopic display. In our first experiment, we examined the effect of stereoscopic display, kinetic depth, and using 3D tubes versus lines to display the links. The results showed a much greater benefit for 3D viewing than previous studies. For example, with both motion and stereoscopic depth cues, unskilled observers could see paths between nodes in 333 node graphs with less than a 10% error rate. Skilled observers could see up to a 1000-node graph with less than a 10% error rate. This represented an order of magnitude increase over 2D display. In our second experiment, we varied both nodes and links to understand the constraints on the number of links and the size of graph that can be reliably traced. We found the difference between number of links and number of nodes to best account for error rates and suggest that this is evidence for a “perceptual phase transition.” These findings are discussed in terms of their implications for information display.

REFERENCES

• 1: Kevin W. Arthur , Kellogg S. Booth , Colin Ware, Evaluating 3D task performance for fish tank virtual worlds, ACM Transactions on Information Systems (TOIS), v.11 n.3, p.239-265, July 1993 [doi>10.1145/159161.155359]
• 2: Bollobas, B. 2001. Random Graphs, 2nd Ed., Theorem 6.19, Cambridge Univ. Press, 151.
• 3: Campbell, F. W. and Green, D. G. 1965. Monocular versus binocular visual acuity. Nature, London 208, 191--192.
• 4: 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
• 5: Frisby, J. P., Buckley, D., and Duke, P. A. 1966. Evidence for recovery of lengths of real objects seen with natural stereo viewing. Perception 25, 129--154.
• 6: Thomas M. J. Fruchterman , Edward M. Reingold, Graph drawing by force-directed placement, Software—Practice & Experience, v.21 n.11, p.1129-1164, Nov. 1991 [doi>10.1002/spe.4380211102]
• 7: Howard, I. P. and Rogers, B. J. 1995. Binocular Vision and Stereopsis. Oxford Psychology Series No 29. Oxford University Press. Oxford.
• 8: Huang, M. L., Eades, P., and Wang, J. 1998. Online animated visualization of huge graphs using a modified spring algorithm. Journal of Visual Languages and Computing 9, 6, 623--645.
• 9: Ernst Kleiberg , Huub van de Wetering , Jarke J. Van Wijk, Botanical Visualization of Huge Hierarchies, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.87, October 22-23, 2001
• 10: T. Munzner, H3: laying out large directed graphs in 3D hyperbolic space, Proceedings of the 1997 IEEE Symposium on Information Visualization (InfoVis '97), p.2, October 18-25, 1997
• 11: Tamara Munzner , Francois Guimbretiere , George Robertson, Constellation: A Visualization Tool for Linguistic Queries from MindNet, Proceedings of the 1999 IEEE Symposium on Information Visualization, p.132, October 24-29, 1999
• 12: Norman, J. F., Todd, J. T., Perotti, V. I., and Tittle, J. S. 1996. The visual perception of 3-D length. Journal of Experimental Psychology: Human Perception and Performance 22, 173--186.
• 13: Parker, G., Franck, G., and Ware, C. 1998. Visualization of large nested graphs in 3D: Navigation and interaction. Journal of Visual Languages and Computing 9, 299--317.
• 14: Catherine Plaisant , Jesse Grosjean , Benjamin B. Bederson, SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.57, October 28-29, 2002
• 15: George G. Robertson , Stuart K. Card , Jack D. Mackinlay, Information visualization using 3D interactive animation, Communications of the ACM, v.36 n.4, p.57-71, April 1993 [doi>10.1145/255950.153577]
• 16: Rogers, B. and Cagnello, R. 1989. Disparity curvatures and the perception of three-dimensional surfaces Nature, London 339, 137--139.
• 17: Sollenberger, R. L. and Milgram, P. 1993. The effects of stereoscopic and rotational displays in a three-dimensional path-tracing task. Human Factors 35, 3, 483--500.
• 18: Tyler, C. 1975. Spatial organization of binocular disparity sensitivity. Vision Research 15, 583--590.
• 19: Uumori, K. and Nishida, S. 1994. The dynamics of the visual system in combining conflicting KDE and binocular stereopsis cues. Perception and Psychophysics 55, 5, 526--536.
• 20: van Ee, R. and Schor, C. M. 2000. Unconstrained stereoscopic matching of lines. Vision Research 40, 151--162.
• 21: Wallach, H. and O'Connell, D. N. 1953. The kinetic depth effect. Journal of Experimental Psychology 45, 205--217.
• 22: Colin Ware , Robert Bobrow, Supporting visual queries on medium-sized node-link diagrams, Information Visualization, v.4 n.1, p.49-58, Spring 2005 [doi>10.1057/palgrave.ivs.9500090]
• 23: Colin Ware , Glenn Franck, Evaluating stereo and motion cues for visualizing information nets in three dimensions, ACM Transactions on Graphics (TOG), v.15 n.2, p.121-140, April 1996 [doi>10.1145/234972.234975]
• 24: Colin Ware , Kevin Arthur , Kellogg S. Booth, Fish tank virtual reality, Proceedings of the INTERACT '93 and CHI '93 conference on Human factors in computing systems, p.37-42, April 24-29, 1993, Amsterdam, The Netherlands [doi>10.1145/169059.169066]
• 25: Wheatstone, C. 1838. Contributions to the physiology of vision. Part the first. On some remarkable and hitherto unobserved phenomena of binocular vision. Philosophical Transactions of the Royal Society 128, 371--394.
• 26: Wills, G. J. 1999. NicheWorks: Interactive visualization of very large graphs. Journal of Computational and Graphical Statistics 8, 2, 190--212

INDEX TERMS

Primary 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)
          Subjects: Evaluation/methodology

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)
          Subjects: Theory and methods

General Terms:
Design, Experimentation, Human Factors

Keywords:
Visualization, graph visualization, network visualization, stereoscopic displays