Elegant representations of graphs in R^3 If I have a graph of a reasonable size (e.g. ~100 nodes, ~40 edges coming out of each node) and I want to represent it in R^3 (i.e. map each node to a point in R^3 and draw a straight line between any two nodes which are connected in the original graph) in a way which would make it easy to understand its structure, what do you think would make a good drawing criterion?
I know this question is ill-posed; it's not objective. The idea behind it is easier to understand with an extreme case. Suppose you have a connected graph in which each node connects to two and only two other nodes, except for two nodes which only connect to one other node. It's not difficult to see that this graph, when drawn in R^3, can be drawn as a straight line (with nodes sprinkled over the line). Nevertheless, it is possible to draw it in a way which makes it almost impossible to see its very simple structure, e.g. by "twisting" it as much as possible around some fixed point in R^3. So, for this simple case, it's clear that a simple 3D representation is that of a straight line. However, it is not clear what this simplicity property is in the general case.
So, the question is: how would you define this simplicity property?
I'm happy with any kind of answer, be it a definition of "simplicity" computable for graphs, or a greedy approximated algorithm which transforms graphs and that converges to "simpler" 3D representations.
Thanks!
EDITED
In the mean time I've put force-based graph drawing ideas into practice and wrote a computer program to simulate how imposing an electrical repulsive force between nodes (Coulomb's Law) and a spring-like behaviour on edges (Hooke's law) would turn out. I've posted the video on youtube. The video starts by randomly generating a graph of 100 nodes each with approximately 1-2 outgoing edges, placing the nodes randomly in 3D space. Then all the forces I mentioned are put into place and the system is left to move around subject to those forces. In the beginning, the graph is a mess and it's very difficult to see the structure. Closer to the end, it is clear that the graph is almost linear. I've also experience with larger-sized graphs but sometimes the geometry of the graph is just a mess and no matter how you plot it, you won't be able to visualise anything. And here is an even more extreme example with 500 nodes.
 A: You might start by exploring the various tools that are available.
For example, Mathematica's GraphPlot3D[] does a nice job with small graphs.
Here is a 5-node graph:
      
And here is a somewhat dense 50-node graph:
      
Both were produced without giving Mathematica any advice.
Like most such tools, it has options for applying different methods, e.g.,
SpringEmbedding.
Edit. As requested by Surikator, here are some random, more-sparse, 50-node graphs:

A: There is a vast literature on Graph Drawing (mostly in two dimensions, but a lot of ideas can be extended to three). The first paper in the subject (almost exactly fifty years ago) was W. Tutte's "How to draw a graph", where the idea was that if you fixed some vertices to be the vertices of a convex polygon, you can make the other vertices satisfy the condition that every vertex is the barycenter of its neighbors. Most of that paper is devoted to a completely incomprehensible argument to show that such drawings are actual embeddings (so no pair of edges crosses) -- this has been reproved (or proved, depending on how cynical you are) by a number of people. That issue does not really arise in three dimensions, however. The Tutte embeddings (which have been generalized in various ways) are discrete harmonic maps.
A: I'll mention this since no-one else has. Maple did it in the deprecated network package and now does it in the plots package as graphplot3d : Make the adjacency matrix of the graph. Then the graphplot3d command will do the following: find three eigenvectors (maybe of unit length) by default for eigenvalues 2,3,4 although you can choose. This give 3 vectors in $\mathbb{R}^n$ It will view them as $n$ triples in $\mathbb{R}^3$ and use these as the vertex locations. Sometimes it works nicely showing off symmetries, other times not so well. Some documentation
I am not praising Maple here rather the method. Below are 3 plots of random sparse 50 vertex graphs. I'd like thicker edges and cute balls at vertices. Also I had to fool around a bit to not have a number at each vertex.
The springs method is nice, and you can probably nudge and shake or pull and release to see what happens. At least in Maple the system of differential equations can start to really bog down for a big graph. I like that the representation by this eigenvalue method is completely determined by the graph. The results can be quite nice, when it works.  I tried the Hoffman Singleton Graph (50 vertices, regular of degree 7) and none of the eigenvector choices I made came out with a nice graph. 
3 graphs http://www.freeimagehosting.net/uploads/2c7605e986.jpg
A: An idea that occurred to me, though I don't know how computationally feasible it is, is to insist all edges are of length one [Edit: this can't be done in general.], put a repelling charge on each vertex, and let the graph float to an equilibrium position. This would be somewhat analogous to the idea of minimizing "knot energy" in the case of embeddings of $S^1$ in $\mathbb R^3$. 
A: complexity(graph,f) := $\displaystyle\sum_{\langle g,r\rangle \in \; \operatorname{graph}^2} \begin{cases} 0 & \text{if }g=r \\\\ \operatorname{log}\left(\frac{d(f(g),f(r))}{d(g,r)}\right)^2 & \operatorname{if }g\neq r\end{cases}$
although I suppose this is more quality of embedding than simplicity ...
A: A truncated icosahedron can be embedded in a plane, but is more symmetrical and easier to understand when embedded in a sphere. This goes for all the Platonic figures and their truncated, rectified, etc. derivatives.
That doesn't really answer the question "what do you think would make a good drawing criterion?" Ok, having a symmetrical embedding in R^3 makes a good drawing criterion.
