Some interesting stuff with VisualMGF (and other tales of bad research)

Another two weeks gone by and what to I have to show for it? Well for starters I'm rather embarrassed, for you see my implementation of "Visual MGF" does not quite work as planned, to such an extent I am genuinely surprised it does what it does at all.

So what disastrous discovery comes this week? For several months it has been explained to my supervisors that the value of k (ideal edge length) for different levels of the multilevel scheme is appropriate following the research in static graph drawing. Technically, this is true and it was expected that the movement between levels (when using the dynamic drawing algorithm) was fine due to the speed at which layout is generated in comparison to a pure multilevel approach.

Well... I am partially wrong. The value itself is fine, my interpolation of layout, not so much. During one iteration of the VisualMGF cycle, each level of the multilevel scheme has force directed placement applied to it once, passing the displacement of vertices to their children in finer graphs (with some small difference to avoid singularities), for the sake of names we call this Cycle A (for Awesome). When the finest graph has layout applied, the algorithm runs in reverse, updating the parent vertices in coarser levels with the averaged layout of their finer children (in order to overcome inaccurate approximations which cause compression in the layout), named Cycle B (for B*****ks). These two update cycles do not work well together, in fact, Cycle A is relatively useless and only aids in expansion of the graph. As Cycle B updates vertices, the layout of the finer graphs is completely re-written to form a coarser layout of the original graph (which at this point can be considered bad layout). 

So how do I get "good" layouts? The MGF Approximation structure maintains approximation of vertex positions and continues to use these to overcome minima. Although this leads to problems with minima (both global and local), the layouts inevitably end up rather appreciable after some time. Removing the extra calculations of applying VisualMGF to the coarser levels (only applying to the original graph) proves that layout in coarser graphs is irrelevant - and provides a noticeable improvement in time required to find layout.

Initially I thought this would only be a problem with the VisualMGF algorithm but it appears to have a worse effect in the standard VisualML (visual multilevel only). Although displacement in the finer graphs is applied, and a good layout can be applied in coarser levels, the layout in the finer levels contradicts the coarser layout and so does not find a good layout so easily (if at all).

So... it seems Veldhuizen does have some tricks up his sleeve which requires yet another revisit to his publication in dynamic graph drawing. So the trick now is to once again identify a method of achieving global layout appropriately, but having used the multilevel scheme already for approximation, what comes next? a multi multilevel scheme? How deep does this rabbit hole go?