Article ID Journal Published Year Pages File Type
431144 Journal of Discrete Algorithms 2008 22 Pages PDF
Abstract

In this paper we consider the problem of finding three-dimensional orthogonal drawings of maximum degree six graphs from the computational complexity perspective. We introduce a 3SAT reduction framework that can be used to prove the NP-hardness of finding three-dimensional orthogonal drawings with specific constraints. By using the framework we show that, given a three-dimensional orthogonal shape of a graph (a description of the sequence of axis-parallel segments of each edge), finding the coordinates for nodes and bends such that the drawing has no intersection is NP-complete. Conversely, we show that if node coordinates are fixed, finding a shape for the edges that is compatible with a non-intersecting drawing is a feasible problem, which becomes NP-complete if 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 drawing with at most two bends per edge and of characterizing orthogonal shapes admitting an orthogonal drawing without intersections.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,