  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 describe a correspondence
between xyz graphs and face-colored embeddings of the graph onto
two-dimensional manifolds, and we relate bipartiteness of the xyz graph to
orientability of the underlying topological surface. Using this correspondence,
we show that planar graphs are xyz graphs if and only if they are bipartite,
cubic, and three-connected, and that it is NP-complete to determine whether an
arbitrary graph is an xyz graph. We also describe an algorithm with running
time O(n 2^{n/2}) for testing whether a given graph is an xyz graph.
