creators_name: Patrignani, Maurizio
editors_name: Healy, Patrick
editors_name: Nikolov, Nikola S.
editors_id: Healy, Patrick
editors_id: Nikolov, Nikola S.
type: confpaper
datestamp: 2006-02-22
lastmod: 2008-09-18 11:09:00
metadata_visibility: show
title: Complexity Results for Three-dimensional Orthogonal Graph Drawing
ispublished: pub
subjects: P.600.700
subjects: G.999
subjects: P.60
full_text_status: none
abstract: We introduce the 3SAT reduction framework which can be used to prove the NP-hardness of finding three-dimensional orthogonal drawings with specific constraints. We use it to show that finding a drawing of a graph whose edges have a fixed shape is NP-hard. Also, it is NP-hard finding a drawing of a graph with nodes at prescribed positions when a maximum of two bends per edge is allowed. We comment the impact of these results on the two open problems of determining whether a graph always admits a 3D orthogonal drawing with at most two bends per edge and of characterizing orthogonal shapes admitting a drawing without intersections.
    
date: 2006
date_type: published
publisher: Springer
pagerange: 368-379
refereed: FALSE
referencetext: T. C. Biedl.: Heuristics for 3D-orthogonal graph drawings Proc. 4th Twente Workshop on Graphs and Combinatorial Optimization, pages 41-44, 1995.

J. A. Bondy and U. S. R. Murty.: Graph Theory with Applications. Macmillan, London, 1976.

F. Brandenburg, D. Eppstein, M. T. Goodrich, S. Kobourov, G. Liotta, and P. Mutzel.: Selected open problems in graph  drawing. G. Liotta, editor, Graph Drawing (Proc. GD 2003), volume 2912 of LNCS, pages 515-539. Springer-Verlag, 2004.

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

E. D. Demaine, J. S. B. Mitchell, and J. O'Rourke, (eds.).: The Open Problems Project. http://cs.smith.edu/~orourke/TOPP/Welcome.html

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

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

G. Di Battista, G. Liotta, A. Lubiw, and S. Whitesides.: Embedding problems for paths with direction constrained edges. Theor. Comp. Sci., 289:897-917, 2002.

E. Di Giacomo, G. Liotta, and M. Patrignani.: A note on 3D orthogonal drawings with direction constrained edges. Inform. Process. Lett., 90:97-101, 2004.

P. Eades, C. Stirk, and S. Whitesides.: The techniques of Kolmogorov 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., 103(1-3):55-87, 2000.

B. Y. S. Lynn, A. Symvonis, and D. R. Wood.:Refinement of three-dimensional orthogonal graph drawings. J. Marks, editor, Graph Drawing (Proc. GD '00), volume 1984 of LNCS, pages 308-320. Springer-Verlag, 2001.

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

M. Patrignani.: Complexity results for three-dimensional orthogonal graph drawing. Tech. Report RT-DIA-94-2005, Dip. Inf. e Automazione, Univ. Roma  Tre, 2005. http://dipartimento.dia.uniroma3.it/ricerca/rapporti/rapporti.php

F. P. Preparata and M. I. Shamos.: Computational Geometry: An Introduction. Springer-Verlag, 3rd edition, Oct. 1990.

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.

D. R. Wood.: On higher-dimensional orthogonal graph drawing. J. Harland, editor, Proc. Computing: the Australasian Theory Symposimum (CATS '97), volume 19, pages 3-8. Australian Computer Science Commission, 1997.

D. R. Wood.: Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. J. of Graph Algorithms and Applications, 7:33-77, 2003.

D. R. Wood.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theor. Comp. Sci., 299:151-178, 2003.

D. R. Wood.: Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout. Algorithmica, 39:235-253, 2004.
citation: Patrignani, Maurizio (2006) Complexity Results for Three-dimensional Orthogonal Graph Drawing. [Conference Paper]