Logo

Login

Orthogonal Drawings with Few Layers

Biedl, Therese and Johansen, John and Shermer, Thomas and Wood, David R. (2002) Orthogonal Drawings with Few Layers. [Conference Paper]

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
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
Deposited By:Arnopolina, Galina
Deposited On:22 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2265&spage=297

Repository Staff Only: item control page

References

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

2. 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.

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

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

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

6. 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.

7. 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.

8. T. Biedl, T. Thiele, and D.R. Wood. Three-dimensional orthogonal graph drawing with optimal volume. In J. Marks [18], pages 284-295.

9. 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.

10. 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.

11. 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.

12. 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.

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

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

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

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

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

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

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

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

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

22. 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.

23. 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.

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

25. 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.

26. 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.

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

28. 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.

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

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

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.