Comment by johndough

In academia, this is called "planar embedding" and can be computed in O(V) where V is the number of vertices of the graph.

However, there are graphs that do not allow planar embeddings (e.g. K_5 or K_3,3, see https://en.wikipedia.org/wiki/Planar_graph).

In this case, you'll probably want to look into heuristics that produce a low number of crossings and little distortion when new vertices are added.