Interesting... Gibberish, but interesting...

<EDIT>
re-reading this, I just remembered, Peter Eades commented on such findings in his "Heuristic for Graph Drawing" note.See section 3: Examples - Figure 1(a) and Figure 1(b). This however, is attempting to highlight that when starting positions remain static, the structure of the graph can cause outcomes like this, even for graphs of similar size. Another comparison has been added below. 31/01/2011
</EDIT>

Just a quick update.

Come across an unusual but almost predictable pattern during my play time. Whilst checking over graphs of reasonable size (~50 vertices) to ensure the coarsening works, I noticed some graphs drew well where others did not. In retaliation, I attacked the initial positions, making them a tenth smaller, only to find the graph that drew badly drew well, and vice versa.

Its hard to explain with text and no images, so here are some images:

This first image shows two graphs of similar size, a 5x5 square matrix, and a honeycomb of 19 hexagons. As can be seen, the matrix has a relatively good layout (ignoring the edges in the background), whereas the honeycomb does not. Note, these are drawn with initial positions of x = i +1, and y = i, where i is the vertex number.

Now for the change, x = i+1/10, and y = i/10

The square matrix has deformed, caused by twisting in the coarsened graphs. The honeycomb, on the other hand, has a reasonably good layout. This shows initial positions of vertices can have an effect on the layout. More tests, including randomised initial positions, will allow me to see whether this is as important as I would like to think.

<EDIT>

Given rand values (using Math.random() to return values of 0.0 >= x,y < 1.0 ), the graphs are very similar to using i+1/10. However, as the initial coordinates are different every time the project is run, the outputs can be different each time (and so there's no guarantee you will see the same aesthetically pleasing layout as before).

</EDIT>

Other changes, such as the number of times the force directed placement algorithm is run, also affect the layout but this is common sense (and is shown in Peter Eades heuristic for Graph Drawing). Why have I included this almost useless point? in case I forget, also, I haven't quoted a paper in a while and feel I may be neglecting them.

Anyway, just felt like updating this little bit, may hopefully of be use one day. All the best.