The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing

Abstract

We consider embeddings of 3-regular graphs into 3-dimensional Cartesian coordinates, in such a way that two vertices are adjacent if and only if two of their three coordinates are equal (that is, if they lie on an axis-parallel line) and such that no three points lie on the same axis-parallel line; we call a graph with such an embedding an xyz graph. We show that planar xyz graphs can be recognized in linear time, but that it is NP-complete to determine whether an arbitrary graph is an xyz graph. We also describe an algorithm with running time O(n2^n/2) for testing whether a given n-vertex graph is an xyz graph.