An Algorithm for Three-Dimensional Orthogonal Graph Drawing

Wood, David R. (1998) An Algorithm for Three-Dimensional Orthogonal Graph Drawing. In: Graph Drawing 6th International Symposium, GD’ 98, August 13-15, 1998 , pp. 332-346(Official URL: http://dx.doi.org/10.1007/3-540-37623-2_25).

Full text not available from this repository.

Abstract

In this paper we present an algorithm for 3-dimensional orthogonal graph drawing based on the movement of vertices from an initial layout along the main diagonal of a cube. For an n-vertex m-edge graph with maximum degree six, the algorithm produces drawings with bounding box volume at most 2.37n^3 and with a total of 7m/3 bends, using no more than 4 bends per edge route. For maximum degree five graphs the bounding box has volume n^3 and each edge route has two bends. These results establish new bounds for 3-dimensional orthogonal graph drawing algorithms and improve on some existing bounds.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-37623-2_25
Classifications: G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.210 Bends
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/337

Actions (login required)

View Item View Item