Elegant representations of graphs in R^3

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:

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.

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