Whenever I have an optimization problem that is difficult to solve, I think of genetic algorithms. My solution below assumes that you are familiar with GA (not very difficult to implement it yourself)
Looking at the example graph you gave, let us suppose that the nodes will be placed on a NxN grid (integer positions), then to codify the genomes, consider the following scheme:
00101 00100 11010 11110 11000
A B C D E
where each part encodes the position in the grid (in binary) of the nodes (in that order). The length of each part depends on the size of the grid ( length=ceil(log2(N*N)) ).
The grid is numbered row by row, left to right.
So as an example, for a complete graph with 4 nodes (A,B,C,D) and a 3x3 grid, the string:
0011 0001 0101 1000 = 3 1 5 8
A B C D A B C D
represents the following layout:
. B . 00 01 02
A . C 03 04 05
. . D 06 07 08
Next we design the crossover operator as usual (one- or two-points crossover), and mutation as well (flip one bit at random). We just have to make sure that at any time, we only have valid positions inside the grid.
Finally the fitness function will be some function of the distances between the nodes on the path (sum for multiple paths), which will penalizes long paths (as a minimization problem).
An example is to take the city-block distance between the nodes.
The rest of the method is the standard genetic algorithm (initialization, evaluation, selection, reproduction, termination).
Example
To illustrate, consider the previous layout with the city-block distance, given the following two paths: A D C B and C B D A
A -> D -> C -> B
3 + 1 + 2 = 6 therefore
C -> B -> D -> A fitness(0011 0001 0101 1000) = 6 + 8 = 14
2 + 3 + 3 = 8
Obviously the goal is to find the layout that minimizes the fitness function.