Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00283
The Complexity of Bendless ThreeDimensional Orthogonal Graph Drawing
Vol. 17, no. 1, pp. 3555, 2013. Regular paper.
Abstract We consider embeddings of 3regular graphs into 3dimensional 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 axisparallel line) and such that no three points lie on the same axisparallel 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 NPcomplete 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 nvertex graph is an xyz graph.

Submitted: July 2012.
Reviewed: October 2012.
Revised: November 2012.
Accepted: January 2013.
Final: January 2013.
Published: January 2013.
Communicated by
Csaba D. Tóth
