xyz Embedding
An 
embedding, also called an "
drawing," is a three-dimensional embedding such that every axis-parallel line contains either zero or two vertices. Such an embedding is a vertex set of a cubic graph in which two vertices are adjacent if and only if two of their three coordinates are equal and each vertex 
is connected to the three other points that lie on the three axis-parallel lines through 
(Eppstein 2008).
A planar graph 
is an 
graph (and hence possesses an 
embedding) if and only if 
is bipartite, cubic, and 3-connected (Eppstein 2008).
For any 
, 
points can be embedded on an 
grid at the points 
satisfying 
, 1 (mod 
) producing an 
embedding of a cubic symmetric graph for each 
(Eppstein 2007a). The following table summarizes the resulting graphs for small 
.
 |
graph |
| 2 |
cubical graph |
| 3 |
Pappus graph |
| 4 |
Dyck graph |
| 5 |
Foster graph 050A |
| 6 |
Foster graph 072A |
| 7 |
Foster graph 098B |
| 8 |
Foster graph 128A |
| 9 |
Foster graph 162A |
| 10 |
Foster graph 200A |
| 11 |
Foster graph 242A |
| 12 |
Foster graph 288A |
| 13 |
Foster graph 338B |
| 14 |
Foster graph 392B |
| 15 |
Foster graph 450A |
| 16 |
Foster graph 512A |
| 17 |
Foster graph 578A |
| 18 |
Foster graph 648A |
| 19 |
Foster graph 722B |
| 20 |
Foster graph 800A |
| 21 |
Foster graph 882B |
| 22 |
Foster graph 968A |
However, there also exist 
embeddings for additional graphs not in this list, including 
, 
(the Nauru graph), 
, 
, and 
(Eppstein 2007b).
REFERENCES
Eppstein, D. "Topology of xyz Graphs." 9 Jun 2006. http://11011110.livejournal.com/56492.html.
Eppstein. D. "Cubic Symmetric xyz Graphs." 16 Oct 2007a. http://11011110.livejournal.com/120326.html.
Eppstein, D. "More on Cubic Symmetric Graphs." 20 Oct 2007b. http://11011110.livejournal.com/120899.html.
Eppstein, D. "The Topology of Bendless Three-Dimensional Orthogonal Graph Drawing." 22 Aug 2008. http://arxiv.org/abs/0709.4087.
