Complexity Results for Three-dimensional Orthogonal Graph Drawing

Patrignani, Maurizio (2006) Complexity Results for Three-dimensional Orthogonal Graph Drawing. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005 , pp. 368-379(Official URL: http://dx.doi.org/10.1007/11618058_33).

Full text not available from this repository.

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.

Item Type: Conference Paper
Additional Information: 10.1007/11618058_33
Classifications: P Styles > P.600 Poly-line > P.600.700 Orthogonal
G Algorithms and Complexity > G.999 Others
P Styles > P.060 3D
URI: http://gdea.informatik.uni-koeln.de/id/eprint/705

Actions (login required)

View Item View Item