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. -
Patrignani, M. (2005). Complexity Results for Three-dimensional Orthogonal Graph Drawing. In Graph Drawing, 13th International Symposium, GD 2005, Lecture Notes in Computer Science 3843 (pp. 368-379). BERLIN HEIDELBERG : Springer-Verlag [10.1007/11618058_33].
Complexity Results for Three-dimensional Orthogonal Graph Drawing
PATRIGNANI, Maurizio
2005-01-01
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. -I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
