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.