Algorithm for a planar graph game

I am looking for an algorithm for the following task:

We are playing the following game : There is a planar graph drawn in front of us, e.g. enter image description here

We can see the edges have intersected each other at 3 places. We are going to move the vertices without deleting any edge, so that the edges don't intersect each other any more. e.g. for the given graph we can do it in the following two steps, by first moving the vertex E, enter image description here

and then by moving the vertex B

enter image description here

This was an extremely easy example. The planar graph given can be much more complicated.

enter image description here

which has to be converted to

enter image description here

Anyone can do it by trial and error, but what is the general algorithm one needs to follow given any planar graph structure.

Any kind of hint or solution is welcome. Thanks in advance! :)

Solution

If the complexity of the solution is of no concern, then there exists a linear-time algorithm to find coordinates for each vertex such that the drawing is straight-line planar. Unfortunately, it's rather involved; the first step is to find a combinatorial planar embedding using, e.g., Boyer--Myrvold (On the Cutting Edge: Simplified O(n) Planarity by Edge Addition, 2004), then converting this combinatorial embedding to a geometric one via Chrobak--Payne (A Linear-time Algorithm for Drawing a Planar Graph on the Grid, 1995). These algorithms are implemented in the Boost Graph Library.

A simpler algorithm that will work most of the time on well connected graphs like your samples is spectral layout. Compute the second and third eigenvectors of the Laplacian matrix and use them as X and Y coordinates.