Dynamic stuff?

So another long delay to an update, so what's been going on?

Primitives

Sadly, no good news here. The primitives work, which intended to reduce the number of levels in a graph and as such, reduce the runtime required for approximating global repulsive forces has had little impact. This is primarily down to primitives only being identified too late on in the coarsening phase (when graphs only consist of 100 or fewer vertices). As a result, the time saved generating this layout is insignificant - and with limits on the extent of approximations, there is no real use for this approach unless a primitive with thousands of vertices is identified.

So, this is apparently a no-go.

Leaf Coarsening

A little better news but still not amazing. The leaf coarsening works as expected, with most graphs being unaffected by the approach, and those graphs which do have leaves in their structure, coming back with reduced runtime (for example, add32 is given a layout in 15% less time).

The layout however, although higher in the number of edge crossings, makes changes more available to users. Leaves are currently laid out using the centroid of the graph to push them outwards (separated by small differences if coincident), however, a technique using a "cone of freedom" allows for multiple coincident vertices to be displayed evenly around an anchoring vertex or between other edges, giving them more freedom to escape repulsive forces and to be displayed as the user requires (through changing the angle of separation between them). Though the technique is not perfected and is more specific to tree and star type graphs, the approach is relatively simple and can provide a more contextual layout.

But unfortunately again, this is no real benefit to general graph drawing and is just a mechanism than only optimises the MGF structure when applicable.

Multimatching

Another disappointment - grouping more than 2 vertices was expected to reduce the number of levels in the multilevel scheme (and MGF tree) making for a faster and more efficient approximation which closer resembles the structure of the quadtree. The results say... sometimes, but each graph has a "preferred" matching number which is cannot be identified without checking each matching number individually (a long process). This essentially rules out multi-matching as a standard mechanism to improve the algorithm.

Summary of MGF Optimisation through Coarsening

Only the leaf coarsening has any promise - and the promise is not particularly linked to general graphs. The primitives layout is only useful for smaller graphs that require perfect layout, and even then, FDP offers competitive speeds. Multimatching backs up the use of matching only singular edges (two vertices), higher matching numbers provide an increase in levels (in general) and an increase in runtime.

Spring Embedder without Cooling Schedule

Previously I have complained that the Fruchterman and Reingold cooling schedule does not meet my demands, and as such, does not bode well for dynamic graph drawing (thus everyone uses Eades spring embedder or similar). The problem comes from the large movement in the beginning of the cooling schedule, and the stopping when the tolerance is met (as the cooling schedule acts as a limit on the number of iterations). Removing such limitation and allowing the algorithm to run indefinitely does not provide good layout as the large movements are never restricted.

Well, finally some good-ish news. Thanks to implementations of the modified spring embedder on GPU's, there is a cooling schedule which allows for continious layout generation without stopping limits, without the erratic movement and with (relatively) good layout. The approach uses two cooling schedules and treats the movement of the two forces seperately (as opposed to one singular movement). After a quick implementation, the layout is achieved smoothly and nicely, albeit with much more noticeable peripheral effect. Hopefully, this discovery will aid my design of the relative dynamic algorithm.

The modified spring embedder without cooling schedule showing the erratic movement as repulsive and attractive forces continually fight each other. The graph drawing is a thee dimensional 7x7x7 vertex grid. No multilevel scheme is used.

The modified spring embedder with two cooling schemes. The erratic movement disappears and allows for continuous layout generation (a layout is achieved and does not change). Unfortunately, as the cooling schedule has not yet been fitted to my own algorithm, the graph expands to a much larger size than required. The same 7x7x7 grid is drawn. Unfortunately, this approach is much slower than the single cooling schedule as it takes longer for vertices to pass out of local minima.

Current Dynamic Framework

Some progress in the dynamic framework. Mechanisms and data structures have been prepared for changes to a graph and updating the layout periodically has been achieved. In the video below you can view the graph 55grid (3025, a 55x55 vertex grid) having vertices removed and the layout updating to show these changes. The structure/mental map of the graph remains until nearly 75% of all edges are removed.

The erratic movement after the layout is updated comes from the cooling  schedule as mentioned above. I am currently implementing the new approach to smoothen this out and so the redrawn layout does not have to be requested but is visualised immediately. An alternate and possible faster approach has been suggested by my supervisor which would be to only show the stages of layout generation where vertex movement is below some tolerance - making the image and changes much smoother.