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.

Abstract

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

References

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.