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 on 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.
Work partially supported by European Commission – Fet Open project COSIN – COevolution and Self-organisation In dynamical Networks – IST-2001-33555, by European Commission – Fet Open project DELIS – Dynamically Evolving Large Scale Information Systems – Contract no 001907, by MIUR under Project ALGO-NEXT (Algorithms for the Next Generation Internet and Web: Methodologies, Design, and Experiments), and by “The Multichannel Adaptive Information Systems (MAIS) Project”, MIUR Fondo per gli Investimenti della Ricerca di Base.
Chapter PDF
Similar content being viewed by others
References
Biedl, T.C.: Heuristics for 3D-orthogonal graph drawings. In: Proc. 4th Twente Workshop on Graphs and Combinatorial Optimization, pp. 41–44 (1995)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications. Macmillan, London (1976)
Brandenburg, F., Eppstein, D., Goodrich, M.T., Kobourov, S., Liotta, G., Mutzel, P.: Selected open problems in graph drawing. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 515–539. Springer, Heidelberg (2004)
Closson, M., Gartshore, S., Johansen, J., Wismath, S.K.: Fully dynamic 3-dimensional orthogonal graph drawing. J. of Graph Algorithms and Applications 5(2), 1–34 (2001)
Demaine, E.D., Mitchell, J.S.B., O’Rourke, J. (eds.): The Open Problems Project, http://cs.smith.edu/~orourke/TOPP/Welcome.html
Di Battista, G., Eades, P., Tamassia, R., Tollis, I.G.: Graph Drawing. Prentice Hall, Upper Saddle River (1999)
Di Battista, G., Liotta, G., Lubiw, A., Whitesides, S.: Orthogonal drawings of cycles in 3d space. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 272–283. Springer, Heidelberg (2001)
Di Battista, G., Liotta, G., Lubiw, A., Whitesides, S.: Embedding problems for paths with direction constrained edges. Theor. Comp. Sci. 289, 897–917 (2002)
Di Giacomo, E., Liotta, G., Patrignani, M.: A note on 3D orthogonal drawings with direction constrained edges. Inform. Process. Lett. 90, 97–101 (2004)
Eades, P., Stirk, C., Whitesides, S.: The techniques of Kolmogorov and Bardzin for three dimensional orthogonal graph drawings. Inform. Process. Lett. 60, 97–103 (1996)
Eades, P., Symvonis, A., Whitesides, S.: Three dimensional orthogonal graph drawing algorithms. Discrete Applied Math. 103(1-3), 55–87 (2000)
Lynn, B.Y.S., Symvonis, A., Wood, D.R.: Refinement of three-dimensional orthogonal graph drawings. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 308–320. Springer, Heidelberg (2001)
Papakostas, A., Tollis, I.G.: Algorithms for incremental orthogonal graph drawing in three dimensions. J. of Graph Algorithms and Applications 3(4), 81–115 (1999)
Patrignani, M.: 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
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction, 3rd edn. Springer, Heidelberg (1990)
Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)
Vijayan, G., Wigderson, A.: Rectilinear graphs and their embeddings. SIAM J. Comput. 14, 355–372 (1985)
Wood, D.R.: On higher-dimensional orthogonal graph drawing. In: Harland, J. (ed.) Proc. Computing: the Australasian Theory Symposimum (CATS 1997), vol. 19, pp. 3–8. Australian Computer Science Commission (1997)
Wood, D.R.: Lower bounds for the number of bends in three-dimensional orthogonal graph drawings. J. of Graph Algorithms and Applications 7, 33–77 (2003)
Wood, D.R.: Optimal three-dimensional orthogonal graph drawing in the general position model. Theor. Comp. Sci. 299, 151–178 (2003)
Wood, D.R.: Minimising the number of bends and volume in 3-dimensional orthogonal graph drawings with a diagonal vertex layout. Algorithmica 39, 235–253 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patrignani, M. (2006). Complexity Results for Three-Dimensional Orthogonal Graph Drawing. In: Healy, P., Nikolov, N.S. (eds) Graph Drawing. GD 2005. Lecture Notes in Computer Science, vol 3843. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11618058_33
Download citation
DOI: https://doi.org/10.1007/11618058_33
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-31425-7
Online ISBN: 978-3-540-31667-1
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science