Orthogonal Drawings of Cycles in 3D Space (Extended Abstract)

Di Battista, Giuseppe and Liotta, Giuseppe and Lubiw, Anna and Whitesides, Sue (2001) Orthogonal Drawings of Cycles in 3D Space (Extended Abstract). In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000 , pp. 272-283(Official URL: http://dx.doi.org/10.1007/3-540-44541-2_26).

Full text not available from this repository.


Let C be a directed cycle, whose edges have each been assigned a desired direction in 3D (East, West, North, South, Up, or Down) but no length. We say that C is a shape cycle. We consider the following problem. Does there exist an orthogonal drawing $\Gamma$ of C in 3D such that each edge of $\Gamma$ respects the direction assigned to it and such that $\Gamma$ does not intersect itself? If the answer is positive, we say that C is simple. This problem arises in the context of extending orthogonal graph drawing techniques and VLSI rectilinear layout techniques from 2D to 3D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-44541-2_26
Classifications: Z Theory > Z.250 Geometry
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/390

Actions (login required)

View Item View Item