Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00283
The Complexity of Bendless Three-Dimensional Orthogonal Graph Drawing
Vol. 17, no. 1, pp. 35-55, 2013. Regular paper.
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(n2n/2) for testing whether a given n-vertex 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
article (PDF)
BibTeX