TOPICS
Search

xyz Embedding


An xyz embedding, also called an "xyz 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 v is connected to the three other points that lie on the three axis-parallel lines through v (Eppstein 2008).

A planar graph G is an xyz graph (and hence possesses an xyz embedding) if and only if G is bipartite, cubic, and 3-connected (Eppstein 2008).

xyzCubicSymmetric

For any n, 2n^2 points can be embedded on an n×n×n grid at the points (x,y,z) satisfying x+y+z=0, 1 (mod n) producing an xyz embedding of a cubic symmetric graph for each n>=2 (Eppstein 2007a). The following table summarizes the resulting graphs for small n.

ngraph
2cubical graph
3Pappus graph
4Dyck graph
5Foster graph 050A
6Foster graph 072A
7Foster graph 098B
8Foster graph 128A
9Foster graph 162A
10Foster graph 200A
11Foster graph 242A
12Foster graph 288A
13Foster graph 338B
14Foster graph 392B
15Foster graph 450A
16Foster graph 512A
17Foster graph 578A
18Foster graph 648A
19Foster graph 722B
20Foster graph 800A
21Foster graph 882B
22Foster graph 968A

However, there also exist xyz embeddings for additional graphs not in this list, including F_(018)A, F_(024)A (the Nauru graph), F_(040)A, F_(042)A, and F_(054)A (Eppstein 2007b).


See also

Cubic Graph, Hamming Graph, Straight Line Embedding

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

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.

Cite this as:

Weisstein, Eric W. "xyz Embedding." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/xyzEmbedding.html

Subject classifications