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: http://dx.doi.org/10.1007/3-540-46648-7_32).

Full text not available from this repository.

Abstract

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
URI:	http://gdea.informatik.uni-koeln.de/id/eprint/359

Actions (login required)

View Item