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, Colonial Williamsburg, VA, USA , 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.
Repository Staff Only: item control page