Graph embedding in 3D grid minimizing edge length

Question

I know that arbitrary graphs can be embedded trivially in $\mathbb{R^3}$ and that planar graphs can be drawn on a plane using Schnyder's grid embedding algorithm after triangulation. And then there is also the $(i, i^2, i^3)$ moment curve approach..

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. 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?

Answer 1

Let me offer two pointers. First, a common optimization is to minimize the number of bends in an orthogonal drawing. For example, here is a 2-bend drawing of $K_7$:
          
           _{(Image from S.-H. Poon's link.)}

There are many papers on this topic. See also my MO question, "Min Bend Orthogonal Knots."

Second, there is a very good quite recent survey:

Handbook of Graph Drawing and Visualization. CRC Press. 2013. See the chapter by Vida Dujmović and Sue Whitesides, "Three-Dimensional Drawings." (CRC link)
          

Answer 2

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:

[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.