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 , pp. 139-154(Official URL:

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-62495-3_44
Classifications: G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D

Actions (login required)

View Item View Item