The Shape of Orthogonal Cycles in Three Dimensions
Let sigma 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 sigma is a shape cycle. We consider the following problem. Does there exist an orthogonal representation I" of sigma in 3D space such that no two edges of I" intersect except at common endpoints and such that each edge of I" has the direction specified in sigma? If the answer is positive, we say that sigma is simple. This problem arises in the context of extending orthogonal graph drawing techniques from 2D to 3D. We give a combinatorial characterization of simple shape cycles that yields linear time recognition and drawing algorithms.
cycles graph drawing 3d orthogonal drawing topology-shape-metrics