A developing topic

For the past few days I have been collecting, preparing and discussing various output drawings from my graph drawing algorithm, comparing to that used by Yifan Hu. It was always an interest how the different approximation techniques affect the output (a bit obvious, considering its the only difference), but it is becoming more and more prevalent in smaller graphs.

The contraction technique causes a final approximation tree with a root and two children; each child with a weight summated from all the vertices it models, which is used when calculating how much force that supernode exerts on a singular vertex. As there are only two children, in comparison to the quadtree's 4, or octree's 8, it causes the graph to warp around the vector seperating them (due to one side of the graph pushing the other away and vice versa instead of an all outward force).

In comparison, the quadtree pushes out in 4 directions, which causes a much more uniform drawing. As mentioned before this technique is more prevalent in smaller graphs, which much large graphs looking much more like they should. As a brief experiment, I took out the weight from the repulsive force function, which as expected, reduced the stretching (unfortunately, it also caused the collapse of global structure, a result of weak repulsive forces between supernodes and vertices).

The future work on matching will provide some more critical evidence to further investigate this effect and how the contraction approximation can be altered to tackle it (without having to match large numbers of vertices - 8+).