Two Algorithms for Three Dimensional Orthogonal Graph Drawing
Eades, Peter and Symvonis, Antonios and Whitesides, Sue (1997) Two Algorithms for Three Dimensional Orthogonal Graph Drawing. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 139-154 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_44).
Full text not available from this repository.
We use basic results from graph theory to design two algorithms for constructing 3-dimesional, intersection-free orthogonal grid drawings of n vertex graphs of maximum degree 6. Our first algorithm gives drawings bounded by an O(\sqrt(n)) \times O(\sqrt(n)) \times O(\sqrt(n)) box; each edge route containing at most 7 bends. The best previous result generated edge routes containing up to 16 bends per route. Our second algorithm gives drawings having at most 3 bends per edge route. The drawings lie in an O(n) \times O(n) \times O(n) bounding box. Together , the two algorithms initiate the study of bends/bounding box trade-off issues for 3-dimensional grid drawings.
Repository Staff Only: item control page