Logo

Login | Create Account

Orthogonal 3D Shapes of Theta Graphs

Di Giacomo, Emilio and Liotta, Giuseppe and Patrignani, Maurizio (2002) Orthogonal 3D Shapes of Theta Graphs. [Conference Paper]

Full text not available from this repository.

Abstract

The recent interest in three dimensional graph drawing has been motivating studies on how to extend two dimensional techniques to higher dimensions. A common approach for computing a 2D orthogonal drawing of a graph separates the task of defining the shape of the drawing from the task of computing its coordinates. First results towards finding a three-dimensional counterpart of this approach are presented in [8,9], where characterizations of orthogonal r epresentations of paths and cycles are studied. In this note we show that the known characterization for cycles does not immediately extend to even seemingly simple graphs such as theta graphs. A sufficient condition for recognizing three-dimensional orthogonal representations of theta graphs is also presented.

Item Type:Conference Paper
Classifications:M Methods > M.999 Others
Z Theory > Z.250 Geometry
P Styles > P.600 Poly-line > P.600.700 Orthogonal
P Styles > P.060 3D
ID Code:296
Deposited By:Martinez Leon, Victoria
Deposited On:01 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2528&spage=142

Repository Staff Only: item control page

References

1. D.S. Archdeacon and J. Sirán. Characterizing planarity using theta graphs. J. Graoh Theory, 27:17-20, 1998.

2. J. Brown, C. Hickman, A. Sokal, and D. Wagner. On the chromatic roots of generalized theta graphs. J. of Combinatorial Theory, Series B, to appear.

3. I. Bruß and A. Frick. Fast interactive 3-D graph visualization. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes in Comput. Sci., pages 99-110. Springer-Verlag, 1996.

4. G. Chartrand and F. Harary. Planar permutation graphs. Ann. Inst. H. Poincaré, Sect B, 3:433-438, 1967.

5. I.F. Cruz and J.P. Twarog. 3D graph drawing with simulated annealing. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes in Comput. Sci., pages 162-165. Springer-Verlag, 1996.

6. G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NL, 1999.

7. G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides. Embedding problems for paths with direction constrained edges. In Annual International Computing and Combinatorics Conference, (COCOON 2000), volume 1858 of Lecture Notes in Comput. Sci., pages 64-73. Springer-Verlag, 2000.

8. G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides. Orthogonal drawings of cycles in 3d space. In J. Marks, editor, Graph Drawing (Proc. GD '00), volume 1984 of Lecture Notes in Comput. Sci., Springer-Verlag, 2001.

9. G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides. Embedding problems for paths with direction constrained edges. J. of Theor. Comp. Sci, 2002, to appear.

10. E. Di Giacomo, G. Liotta, and M. Patrignani. On orthogonal 3d shapes of theta graphs. Tech. Report RT-DIA-71-2002, Dept. of Computer Sci., Univ. di Roma Tre, 2002. http://web.dia.uniroma3.it/research/.

11. D. Dodson. COMAIDE: Information visualization using cooperative 3D diagram layout. In F.J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes in Comput. Sci., pages 190-201. Springer-Verlag, 1996.

12. D. Eichhorn, D. Mubayi, K. O'Bryant, and D.B. West. Edge-bandwidth of theta graphs. J. Graph Theory, 35:89-98, 2000.

13. F. Harary. Graph Theory. Addison Wisley, Reading, Mass., 1969.

14. T. Jiang, D. Mubayi, A. Shastri, and D.B. West. Edge-bandwidth of graphs. SIAM Journal on Discrete Mathematics, 12(3):307-316, 1999.

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

16. G. Peck and A. Shastri. Bandwidth of theta graphs with short paths. Discrete Mathematics, 103, 1992.

17. I. Sciriha and S. Fiorini. On the characteristic polynomial of homeomorphic images of a graph. Discrete Mathematics, 174:293-308, 1997.

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

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

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.