I know that arbitrary graphs can be [embedded trivially](http://en.wikipedia.org/wiki/Graph_embedding#Embeddings_of_graphs_into_higher-dimensional_spaces) in $\mathbb{R^3}$ and that planar graphs can be drawn on a plane using [Schnyder's grid embedding algorithm](https://www.ics.uci.edu/~eppstein/gina/schnyder/) after triangulation. And then there is also the $(i, i^2, i^3)$ [moment curve approach](http://en.wikipedia.org/wiki/Graph_embedding#Embeddings_of_graphs_into_higher-dimensional_spaces)..


What I am looking for is a non-crossing embedding of arbitrary graphs in multiple coplanar two-dimensional layers within $\mathbb{R^3}$ (a stack of $\mathbb{R^2}$ planes, $\mathbb{R^2} \times \mathbb{Z}$, discretized $\mathbb{R^3}$, 3D grid) just like the moment curve. But to make things more interesting I'd like the resulting embedding to look *nice*, i.e. minimizing the number of layers needed for an embedding and/or minimizing edge length. (Probably I want an embedding in $\mathbb{Z}^3$ or an minimum node distance constraint $|v\_i - v\_j| \ge 1$ for this to make sense)


I am new to this, so pointers to literature or more appropriate search keywords are highly welcome too. Perhaps this is a special/relaxed case of *realization* where distances between neighbors should be $1$, or maybe it is something along the lines of [chip layout optimization](http://link.springer.com/article/10.1007%2FBF01759038). Does it make a difference if the graph is sparse? Is there a theory about embedding planar graphs in $\mathbb{R}^3$ to get shorter edge length?



Graph embedding in 3D grid minimizing edge length
To answer my own question StackExchange style:


The concept you are looking is called [geometric] **thickness** of a graph. As described in the *Handbook of Graph Drawing and Visualization* (p. 473) mentioned by Joseph O'Rourke's excellent answer:



> 
> The thickness of a graph $\mathbf{G}$, denoted by $\theta(\mathbf{G})$, is the minimum $k \in \mathbb{N}$ such that the edge set of $\mathbf{G}$ can be partitioned into $k$ planar subgraphs.
> 
> 
> 


Or as in an [answer on planar graphs by David Eppstein](https://mathoverflow.net/a/7852/47356):



> 
> [Thickness is] the minimum number of colors one needs to color the edges in a drawing of the graph in the plane such that edges of the same color do not cross.
> 
> 
> 


Given such an edge coloring drawing the graph becomes a matter of drawing planar same-color subgraphs each on its own layer. Bad news is that obtaining the coloring or even testing for the minimum $k$ seems to be $\mathcal{NP}$-complete. Also edges are not necessarily short.


Indeed a more practical approach might be to construct an **orthogonal drawing** with known limits to both *bends* and *volume* (and therefore average edge length) as also suggested by Joseph O'Rourke. The *Handbook of Graph Drawing and Visualization* refers to various such constructions in chapter 14: *Three-dimensional drawing algorithms*. 


