Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract)

Wood, David R. (1999) Multi-dimensional Orthogonal Graph Drawing with Small Boxes(Extended Abstract). In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 311-322(Official URL:

Full text not available from this repository.


In this paper we investigate the general position model for the drawing of arbitrary degree graphs in the D-dimensional (D \ge 2) orthogonal grid. In this model no two vertices lie in the same grid hyperplane. We show that for D \ge 3, given an arbitrary layout and initial edge routing a crossing-free orthogonal drawing can be determined. We distinguish two types of algorithms. Our layout-based algorithm, given an arbitrary fixed layout, determines a degree-restricted orthogonal drawing with each vertex having aspect ratio two. Using a balanced layout this algorithm establishes improved bounds on the size of vertices for 2-D and 3-D drawings. Our routing-based algorithm produces 2-degree-restricted 3-D orthogonal drawings. One advantage of our approach in 3-D is that edges are typically routed on each face of a vertex; hence the produced drawings are more truly three-dimensional than those produced by some existing algorithms.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_32
Classifications: G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
P Styles > P.999 Others

Actions (login required)

View Item View Item