Drawing Stressed Planar Graphs in Three Dimensions

Eades, Peter and Garvan, Patrick (1996) Drawing Stressed Planar Graphs in Three Dimensions. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 212-223 (Official URL: http://dx.doi.org/10.1007/BFb0021805).

Full text not available from this repository.


There is much current interest among researches to find algorithms that will draw graphs in three dimensions. It is well known that every 3-connected planar graph can be represented as a strictly convex polyhedron. However, no practical algorithms exist to draw a general 3-connected planar graph as a convex polyhedron. In this paper we review the concept of a stressed graph and how it relates to convex polyhedra; we present a practical algorithm that uses stressed graphs to draw 3-connected planar graphs as strictly convex polyhedra; and show some examples.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021805
Classifications:P Styles > P.720 Straight-line
P Styles > P.060 3D
ID Code:128

Repository Staff Only: item control page


H. S. M. Coxeter. Regular Polytopes. Dover, NY, 1973.

I. Cahit. Drawing the Complete Graph in 3-D with Straight Lines and Without Crossings. Bulletin of the ICA, Vol 12, Sep 94.

R. F. Cohen, P. Eades, T. Lin, and F. Ruskey. Three-Dimensional Graph Drawing. Proc. Graph Drawing 94. Lecture Notes in Computer Science. Volume 894, 1-11. Springer-Verlag, Berlin, 1995.

G. Das, M. T. Goodrich. On the Complexity of Approximating and Illuminating Three-Dimensional Convex Polyhedra. To appear, WADS 1995.

R. Davidson and D. Harel. Drawing Graphs Nicely Using Simulated Annealing, Technical Report CS89-13, Department of Applied Mathematics and Computer Science, The Weizmann Institute of Science, Rehovot, Israel, July 1989.

T. M. J. Fruchtermann and E. M. Reingold. Graph Drawing by Force-directed Placement. Software - Practice and Experience, vol. 21(11), 1129-1164 (Nov 1991).

B. Grünbaum. Convex Polytopes. Wiley, NY, 1967.

B. Grünbaum and G. C. Shephard. Duality of Polyhedra. In Shaping Space: A Polyhedral Approach. Birkhauser, Boston, 1988.

J. E. Hopcroft and P.J. Kahn. A Paradigm for Robust Geometric Algorithms. Algorithmica (1992) 7:339-380.

C. L. Liu. Introduction to Combinatorial Mathematics. McGraw-Hill, NY, 1968.

J. C. Maxwell. On Reciprocal Figures and Diagrams of Forces. Phil. Mag. S. 4. vol. xxvii. (1864) pp.250-261

T. Nishizeki and N. Chiba. Planar Graphs: Theory and Algorithms. Annals of Discrete Mathematics, Volume 32. North-Holland, Netherlands, 1988.

W. T. Tutte. How to Draw a Graph. Proc. London. Math. Soc. (3), 13 (1963), 743-768.