Logo

Login | Create Account

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). [Conference Paper]

Full text not available from this repository.

Abstract

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
Classifications:Z Theory > Z.250 Geometry
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:390
Deposited By:Selbach, Anna
Deposited On:30 Nov 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=1984&spage=272

Repository Staff Only: item control page

References

T. C. Biedl. Heuristics for 3d-orthogonal graph drawings. In Proc. 4th Twente Workshop on Graphs and Combinatorial Optimization, pp. 41-44, 1995.

T. Biedl, T. Shermer, S. Wismath, and S. Whitesides. Orthogonal 3-D graph drawing. J. Graph Algorithms and Applications, 3(4):63-79, 1999.

R. F. Cohen, P. Eades, T. Lin and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199-208, 1997.

G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing. Prentice Hall, 1999.

G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides. Embedding problems for paths with direction constrained edges. In D.-Z. Du, P. Eades, V. Estivill-Castro, paths with direction constrained edges. In D.-Z. Du, P. Eades, V. Estivill-Castro, X. Lin, and A. Sharma, eds., Computing and Combinatorics, 6th Ann. Int. Conf., COCOON 2000, Springer-Verlag LNCS vol. 1858, pp. 64-73, 2000.

G. Di Battista and L. Vismara. Angles of planar triangular graphs. SIAM J. Discrete Math., 9(3):349-359, 1996.

P. Eades, C. Stirk,and S. Whitesides. The techniques of Komolgorov and Bardzin for three dimensional orthogonal graph drawings. Inform. Process. Lett., 60:97-103, 1996.

P. Eades, A. Symvonis , and S. Whitesides. Three-dimensional orthogonal graph drawing algorithms. Discrete Applied Math., vol. 103, pp. 55-87, 2000.

A. Garg. New results on drawing angle graphs. Comput. Geom. Theory Appl., 9(1-2):43-82, 1998. Special Issue on Geometric Representations of Graphs, G. Di Battista and R. Tamassia, eds..

A. Papakostas and I. Tollis. Algorithms for incremental orthogonal graph drawing in three dimensions. J. Graph Algorithms for incremental orthogonal graph drawing in three dimensions. J. Graph Algorithms and Appl., 3(4):81-115, 1999.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.

G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14:355-372, 1985.

V. Vijayan. Geometry of planar graphs with angles. In Proc. 2nd Annu. ACM Sympos. Comput. Geom., pp. 116-124, 1986.

D. R. Wood. Two-bend three-dimesional orthogonal grid drawing of maximum degree five graphs. TR 98/03, School of Computer Science and Software Engineering, Monash University, 1998.

D. R. Wood. An algorithm for three-dimensional orthogonal graph drawing. In S. Whitesides, ed., Graph Drawing (6th Int. Symp., GD '98), Springer-Verlag, LNCS vol. 1547, pp. 332-346, 1998.

D. R. Wood. Three-Dimensional Orthogonal Graph Drawing. Ph.D. thesis, School of Computer Science and Software Engineering, Monash University, 2000.

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.