The simplest way would be to create a known-planar graph, then arrange the vertices in random order in the initial circle, preserving edges. If you assume a simple two-dimensional array, each vertex could have 8 edges, and you're guaranteed not to intersect. Just connect each one together in a chain, then add however many other connections you like at random.

Of course, the cynic in me isn't convinced that anything except the initial placement of the vertices is random - but I'm not curious enough to do the work required to test that theory.

(Disclaimer: at a glance)