"negative results are still results... even twenty thousand of them"

I do love Big Bang Theory, anyway, topic of the day - comparable results.

<Edit> I have since found the cause of the neglected global layout, and a fix is being developed. New results will be published when attained </Edit>

After the success of getting the skeleton of a multi-level force directed placement algorithm implemented, a means of checking the range of edge length and counting edge crossings, it was time to see what would happen with graphs of significant size. My predictions involved fire and computers falling from the sky, fortunately I was wrong and received reasonable-ish results.

NB: the implementation noted above, does not include many features of other graph drawing algorithms, such as C.Walshaws variable edge length for each level, or Fruchterman and Reingolds 'grid variant' to determine the strength of global forces. All graphs are displayed in Euclidean space.

# FDP was applied 500 times per iteration thus the extensive running times in larger graphs, the extensive iteration count is so the local layout can be perfected, so I can see where issues are.
# Graphs taken from C.Walshaws partitioning repository: http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/
# Simply drawing the larger graphs is a time consuming activity, in some cases, 1/4 of the runtime

Results

Graph	|V|	|E|	Runtime (ms)	Levels	Crossings	Average Edge	Largest Edge	Smallest Edge
k33.graph	6	9	275	3	3	1.755	2.89	1.27
cube.graph	8	12	249	3	2	1.93	2.5	1.36
disjoint2.graph	11	13	295	4	0	1.5	1.85	1.26
4grid.graph	16	24	391	4	0	2.04	2.38	1.75
HenHar.graph	19	45	628	6	28	2.34	4.51	1.22
disjoint5.graph	22	23	-	-	-	-	-	-
hex24.graph	24	30	536	6	0	2.2	2.94	1.78
9cube.graph	32	64	827	5	18	2.62	4.05	1.19
25square.graph	36	60	1322	6	4	2.55	4.25	1.26
hex54.graph	54	72	1768	7	0	2.65	3.65	1.95
add20	2395	13722	2966044	370	407983	78.78	73754.48	0.34
data.graph	2851	15093	6725219	13	85514	7.21	213.24	0.01
55grid.graph	3025	5940	3353044	12	15524	16.98	13925.83	1.35
3elt.graph	4720	13722	2147483647	14	-	-	-	-
finan512.graph	74752	261120	3510750	370	415477	82.45	73826.44	0.1

(General) Conclusions

As this is preliminary testing, there is a certain obviousness that results will not yet compete against already existing drawing algorithms. However, these results are very slow (for larger graphs) and the number of edge intersections in each of the graphs are above what you would expect, similarly, the range of edge lengths is too large, especially in the large graphs. These observations mean nothing alone, but when coupled with the visual feedback during the placement of the finest graph, the behaviour of the algorithm can be viewed and more useful conclusions can be made.

As can be seen, the local layout is perfected by the large amount of FDP applied, but the global layout is having an issue. Causes for this is most definitely within the multilevel part of the implementation and investigation will be undertaken as to why this is happening.

(Pretty Pictures) Graph; graphics

9cube.graph - 9 cubes in a 3x3grid

As can be seen, the layout is aesthetically pleasing and matches the expected/typical layout of this graph. The bowing of the edges is a result of global forces pulling the centre vertices outwards (can be fixed by using FR grid variant).

The graph below is of grid55, a 55x55 vertex grid. Although the overall layout is not aesthetically pleasing, investigating the structure at a local level reveals the expected grid layout. This suggests that the global untangling is not sufficient.

The graph below is of add20, and once again, the layout is not pleasing. This graph has the largest number of coarse levels due to its star-like mini-structures, as mentioned in previous posts. This can be verified by looking at the smaller structures within the graph. Global untangling proving an issue here to.

This graph is of data, and shows the global untangling problem again. Although not resembling its ideal layout, the information of the graph is still relevant, for example, there are 3 parts of the graph which are very loosely connected to the overall structure, which was also commented upon in C.Walshaw's "Multilevel Force-Directed Placement".

This is 3elt, which took too long to finish finding a layout. It also displays the global untangling problem but still shows its mesh like local structure.

Now for an interesting look at what's actually happening; 

From left to right, this is how the final graph is given its layout. In the first iteration of the FDP, it appears each of the centre vertices (of which there are very few, so possibly several vertices in the same position), splits into its respective vertices and spreads around it in a circular fashion. In the second iteration, the vertices spread again, outwards until the circle of vertices is larger. In a later iteration, these concentric circles can be seen clearly, and the graph begins to take its shape.

This suggests the multilevel part of the algorithm does very little, and so should be investigated.

Graph; Descriptions

• cube.graph - a simple cube of 8 vertices each with a degree of 3
• disjoint2.graph - a small graph comprised of two individual disconnected graphs
• disjoint5.graph - similar to above, but with 5 graphs. This show an issue with the current mechanism for testing if a graph is coarse enough (|v| =< 2), as 5 components coarsens into disconnected vertices, the algorithm will keep attempting to coarsen the graph until out of memory.
• 4grid.graph - a grid of 4x4 vertices
• 25square.graph - a graph of 6x6 vertices (5x5 squares thus the inaccurate name)
• 55grid.graph - a 55x55 vertex grid
• hex24.graph and hex54.graph - a honeycomb structure of hexagons, with 24 and 54 vertices respectively
• add20.graph - a graph used as an example for most general graph drawing algorithms, modelling an adder
• data.graph - used by C.Walshaw and part of his partitioning archive
• 3elt.graph - as above, also popular as an example among graph drawing algorithms
• finan512.graph - much larger than other tests, but has a very unique structure, and so wanted to test how the algorithm would react to such a graph

Next?
Figure out why the global forces are drawing graphs as a circle/mess of vertices. Also, implement other parts of the multilevel graph drawing algorithm, such as a mechanism to determine short and long range forces. There are many more improvements I could list, but for now, I will update you all as I go.