title: Complexity Results for Three-dimensional Orthogonal Graph Drawing
creator: Patrignani, Maurizio
subject: P.600.700 Orthogonal
subject: G.999 Others
subject: P.060 3D
description: 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.      
publisher: Springer
contributor: Healy, Patrick
contributor: Nikolov, Nikola S.
date: 2006
type: Conference Paper
type: NonPeerReviewed
identifier: Patrignani, Maurizio (2006) Complexity Results for Three-dimensional Orthogonal Graph Drawing. [Conference Paper]
relation: http://gdea.informatik.uni-koeln.de/705/