The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing - Eppstein, David (Journal of Graph Algorithms and Applications, 2013)
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(n2n/2) for testing whether a given n-vertex graph is an xyz graph.