Quick

Just a quick post given its the end of the week and I haven't updated in a while.

This week I have rewritten the Quad Tree approximation algorithm again, and finally I have some accurate results. Due to some discrepencies (the likes of which are still being questioned) being fixed, both approximations (and the results of using normal multilevel with no approximation) follow the curve shown previously by the contraction approximation.

Unfortunately, the edge crossings still look quite unhappy, with quad tree providing less crossings in most cases. However, the difference in runtime can still be observed (note, it appears quad tree gets faster than contraction as the force multiplier gets higher, but at these sizes, crossings are very high and so the speed is useless).

The results show that there is a range 1where the values of the force multiplier allow for good layouts to be given (in terms of edge crossings), so I will now concentrate my efforts on these values. My aim is to decrease the number of edge crossings at the expense of runtime - hopefully so runtime can match that of the quad tree but with better results (if not the same...).

I am also hoping to test coarsening of multiple vertices to see how the quad tree can compare to the structured approach (my prediction is that contraction will perform better due to the approximation using the relationships).

However, these are small in comparison to the next big jump, the paper writing and hopefully, moving to the dynamic layouts. I will update with some charts to show the new results next week (its 7:15pm on Friday now and have lost the patience of uploading images with Blogger).

Have a good weekend!