Funny thing: all my results are worthless (or are they?)

 

It's one of those days... Let me set the scene using my amazing descriptive powers; picture me sat at a desk. A light above me. Carpet Below.

I should never become a novelist...

But back to reality now, I spent yesterday evening making notes and (finally) planning for the arduous paper writing task ahead. As I was working through how to describe my algorithm and its differences to others, I noticed a large and quite significant difference between mine and the quad tree approach used by Yifan Hu; the quad tree is created for each graph in the multilevel scheme, whereas the contraction tree is made once during the coarsening stage (Captain Obvious FTW).

This leaves a large gap of updating the tree. The quad tree does not concern itself with coarse vertex positions after they have been expanded in a finer graph, and so only needs to create a new structure around the finer graph. In the contraction tree, the structure uses the positions of the coarser graphs (parents of vertices and parents of parents), meaning we have to concern ourselves with updated the tree.

Previous to this, the position of coarser vertices are those that were calculated last (when the algorithm gives placement to each graph at a time). This has the consequence that if positions of vertices in a finer graph G(i) change by a large amount, the position of the parents in G(i+n) will no longer accurately model those vertices, and so the approximation loses accuracy.

It is surprising that this did not affect the drawings of the CA approach in a more significant way, but now explains why there is such a difference in both runtime and drawing quality. I have since implemented a method for the update of the contraction tree which will update the parents positions to better model the children.

The beauty of this is that (sacrificing the decreased runtime) I should be able to get better quality drawings, whilst still having the option to ignore quality and concentrate on runtime (a feature not seen in my implementation of the quad tree). The better news, is that this problem will have implications in my future work of dynamic graph drawing, when I will need to update the parents of vertices (in coarser graphs).

Results from previous tests are still valid and will act as one half of the testing data, or what shall be known as "Fast Mode". I am preparing a second lot of tests for the new "Quality Mode", and will continue my paper planning/writing with minimal interference.