Finding the Best Viewpoints for Three-Dimensional Graph Drawings

Eades, Peter and Houle, Michael E. and Webber, Richard (1998) Finding the Best Viewpoints for Three-Dimensional Graph Drawings. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997, Rome, Italy , pp. 87-98 (Official URL:

Full text not available from this repository.


In this paper we adress the problem of finding the best viewpoints for three-dimensional straight-line graph drawings. We define goodness in terms of preserving the relational structure of the graph, and develop two continuous measures of goodness under othographic parallel projection. We develop Voronoi variants to find the best viewpoints under these measures, and present results on the complexity of these diagrams.

Item Type:Conference Paper
Additional Information:10.1007/3-540-63938-1_53
Classifications:P Styles > P.720 Straight-line
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
ID Code:71

Repository Staff Only: item control page


P. Agarwal: Intersection and Decomposition Algorithms for Planar Arrangements, 1991; Cambridge University Press

F. Aurenhammer: "Voronoi Diagrams - A Survey of a Fundamental Geometric Data Structure" in ACM Comp. Surveys, Sep 1991; 23(3)

F. Aurenhammer, H. Edelsbrunner: "An Optimal Algorithm for Constructing the Weighted Voronoi Diagramm in the Plane" in Patt. Recog., 1984; 17(2):251-257

P. Bose, F. Gomez, P. Ramos, G. Toussaint: "Drawing Nice Projections of Objects in Space" in Graph Drawing (Sep 1995; Passau, Germany); pp. 52-63

B. Chazelle, H. Edelsbrunner: "An Optimal Algorithm for Intersecting Line Segments" in IEEE Found. Comp. Sc. (1988)

R. Cohen, P. Eades, T. Lin, F. Ruskey: "Three-Dimensional Graph Drawing" in Algorithmica, 1996; 17(2)

F. Dehne, R. Klein: "The Voronoi Diagram of Points on a Cone"; School of Computer Science, Carleton University, Ottawa

G. Di Battista, P. Eades, R. Tamassia, I. Tollis: "Algorithms for Drawing Graphs: An Annotated Bibliography", Jun 1994;

P. Eades, W. Lai, K. Misue, K. Sugiyama: "Preserving the Mental Map of a Diagram", 1991; Research Report IIAS-RR-91-16E, Fujitsu Laboratories Ltd., Japan

P. Eades, J. Marks, S. North: "Graph Drawing Contest Report" in Graph Drawing (Sep 1996; Berkley, U.S.A.); pp. 129-138

FADIVA,VIRI: "Actual Listing of Information Visualization Systems", 1995;

J. Foley, A. van Dam, S. Feiner, J. Hughes: Computer Graphics: Principles and Practice, 2nd Ed., 1990; Addison-Wesley

S. Fortune: "A Sweepline Algorithm for Voronoi Diagrams" in Algorithmica, 1987; 2(2):153-174

T. Kamada, S. Kawai: "A Simple Method for Computing General Position in Displaying Three-Dimensional Objects" in Comp. Vision, Graphics and Image Processing, 1988; 41:43-56

D. Kirkpatrick: "Optimal Search in Planar Subdivisions" in SIAM J. Comp., 1983; 12(1):28-35

H. Koike: "An Application of Three-Dimensional Visualization to Object-Oriented Programming" in Proc. Adv. Visual Interfaces (1992); pp. 180-192

C. Livingston: Knot Theory, 1993; Math. Assoc. America

T. Munzner, P. Burchard: "Visualizing the Structure of the World Wide Web in 3D Hyperbolic Space" in VRML (Dec 1995; San Diego, U.S.A.); pp. 33-38

F. Preparata, M. Shamos: Computational Geometry: An Introduction, 1985; Springer Verlag

B. Regan: "Information Diagrams for the DOOMed Generation" in Visual (Feb 1996; Melbourne, Australia); pp. 557-566

Silicon Graphics Inc.: "ivview"; UNIX Manual Page

E. Trichina, B. Thomas: "3D Interactive Animation for Visualization of Parallel Design", 1995; Technical Report CIS-96-001, University of South Australia

C. Ware, G. Franck: "Evaluating Stereo and Motion Cues for Visualizing Information Nets in Three Dimensions" in ACM Trans. Graphics, Apr 1996; 15:121-140

C. Ware, D. Hui, G. Franck: "Visualizing Object Oriented Software in Three Dimensions" in CASCON (1993)