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 more sparse random, more-sparse, 50-node graphs:


