Orthogonal Drawings with Few Layers

Biedl, Therese and Johansen, John and Shermer, Thomas and Wood, David R. (2002) Orthogonal Drawings with Few Layers. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 297-311 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_24).

Full text not available from this repository.

Abstract

In this paper, we study 3-dimensional orthogonal graph drawings. Motivated by the fact that only a limited number of layers is possible in VLSI technology, and also noting that a small number of layers is easier to parse for humans, we study drawings where one dimension is restricted to be very small. We give algorithms to obtain point-drawings with 3 layers and 4 bends per edge, and algorithms to obtain box-drawings with 2 layers and 2 bends per edge. Several other related results are included as well. Our constructions have optimal volume, which we prove by providing lower bounds.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_24
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.210 Bends
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:517

Repository Staff Only: item control page

References

T. Biedl. 1-bend 3-D orthogonal box-drawings: Two open problems solved. J. Graph Algorithms Appl., 5(3):1-15, 2001.

T. Biedl, T. Chan, Y. Ganjali, M. Hajiaghayi, and D.R. Wood. Balanced vertex-orderings of graphs. Technical Report CS-AAG-2001-01, Basser Department of Computer Science, The University of Sydney, Australia, 2001.

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

T. C. Biedl. Three approaches to 3D-orthogonal box-drawings. In Whitesides [24], pages 30-43.

T. Biedl and G. Kant. A Better Heuristic for Orthogonal Graph Drawings. Comput. Geom. Theory Appl., 9:159-180, 1998.

T. Biedl and M. Kaufmann. Area-efficient static and incremental graph drawings. In 5th European Symposium on Algorithms, vol. 1284 of LNCS, pages 37-52. Springer-Verlag, 1997.

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

T. Biedl, T. Thiele, and D.R. Wood. Three-dimensional orthogonal graph drawing with optimal volume. In J. Marks editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS. Springer, 2001., pages 284-295.

M. Closson, S. Gartshore, J. Johansen, and S.K. Wismath. Fully dynamic 3-dimensional orthogonal graph drawing. J. Graph Algorithms Appl., 5(2):1-34, 2000.

G. Di Battista, M. Patrignani and F. Vargiu. A split&push approach to 3D orthogonal drawing. J. Graph Algorithms Appl., 4(3):105-133, 2000.

P. Eades, C. Stirk, S. Whitesides. The Techniques of Kolmogorov and Barzdin for Three Dimensional Orthogonal Graph Drawing. Inform. Proc. Lett., 60(2):97-103, 1996.

P. Eades, A. Symvonis, and S. Whitesides. Two Algorithms for Three Dimensional Orthogonal Graph Drawing. In Proc. of the Symp. on Graph Drawing, GD'96, pages 139-154. Springer Verlag, September 1996.

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

K. Hagihara, N. Tokura, and N. Suzuki. Graph embedding on a three dimensional model. Systems-Comput.-Controls, 14(6):58-66, 1983.

A.N. Kolmogorov and Ya.M. Brazdin. About realisation of sets in 3-dimensional space. Problems in Cybernetics. March 1967, pages 261-268.

A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica 8 (1988), 261-277.

B.Y.S. Lynn, A. Symvonis, and D.R. Wood. Refinement of three-dimensional orthogonal graph drawings. In Marks [18], pages 308-320.

J. Marks, editor, Proc. Graph Drawing: 8th International Symposium (GD '00), vol. 1984 of LNCS. Springer, 2001.

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

A. Papakostas and I.G. Tollis. Efficient orthogonal drawings of high degree graphs. Algoritmica, 26: 100-125, 2000.

J. Peterson. Die Theorie der regulären Graphen. Acta. Math., 15:193-220, 1981.

C. Ware and G. Franck. Viewing a graph in a virtual reality display is three times as good as a 2D diagram. In A.L. Ambler and T.D. Kimura, editors, Proc. IEEE Symp. on Visual Languages (VL '94), pages 182-183. IEEE, 1994.

C. Ware and G. Franck. Evaluating stereo and motion cues for visualizing information nets in three dimesions. ACM Transactions on Graphics, 15(2):121-140, 1996.

S. Whitesides, editor. Proc. Graph Drawing: 6th International Symp. (GD '98), volume 1547 of Lecture Notes in Comput. Sci. Springer, 1998.

D.R. Wood. The DLM algorithm for three-dimensional orthogonal graph drawing in the general position model. Submitted; see Technical Report CS-AAG-2001-04, Basser Department of Computer Science, The University of Sydney, 2001.

D.R. Wood. Minimising the number of bends and volume in three-dimensional orthogonal graph drawing with a diagonal vertex layout. Submitted; see Technical Report CS-AAG-2001-03, Basser Department of Computer Science, The University of Sydney, 2001.

D. R. Wood. An algorithm for three-dimensional orthogonal graph drawing. In Whitesides [24], pages 332-346.

D. R. Wood. Multi-dimensional orthogonal graph drawing with small boxes. In J. Kratochvíl, editor, Proc. Graph Drawing: 7th International Symp. (GD '99), Lecture Notes in Comput. Sci., pages 311-322. Springer. 1999.

D. R. Wood. Boundeed degree book embeddings and three dimensional orthogonal graph drawing. Submitted, 2001.

D. R. Wood. Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. In Marks [18], pages 259-271.