Slight Update

Unfortunately there is little to update upon over the past few weeks. Since approval of my MPhil to PhD transfer (only a year late...), I have been generating a short presentation to identify my current position, and any previous and future works for discussion during the viva. I have also been adding to my draft thesis with the hope it shows my examiners that I will be able to complete the PhD within the 3 year limit (only 11months to go!) and that I have a clear plan of what I intend to do in the future.

Much of the presentation is now complete and the thesis is starting to take shape, but there is still a lot of work to be done before it can be considered a complete first draft - but I'm slowly getting there...

As for programming and implementation, little has been made to progress through the dynamic graph drawing stuff, and little will be done until after this viva. When I do return however, it is planned for me to move straight to the dynamic matching work so we can tackle the pesky operations and their effect on the multilevel stuff. Who knows, maybe another paper out of it? Just another idea to add to my growing list of abstracts.

I probably wont update again until the viva is completed, so until next time, enjoy yourself!

What is brute force... What is normal...

Welcome back to another episode of me complaining.

I have failed at implementing a brute force multilevel dynamic graph drawing algorithm. Outputting the changes in coordinates as changes occur is easy enough, but cascading a layout through the coarser levels is not, all due to the number of movements per level. For example, a coarse graph of 2 vertices has 2 movements, but its finer graph of 16 vertices would have 16 movements, which when used to update the coarser graph, causes erratic behavior (shrinking and expanding the graph erratically with no layout).

In this instance, I had expected the weights of vertices, and the difference of k between levels (sqrt(4/7) as given by Walshaw), would have prevented this, apparently I am wrong (or there is a bug I haven't found yet). This type of behavior has been covered and tackled by Veldhuizen through use of damping and time dilation mechanisms, suggesting Veldhuizens approach is actually brute force, adapted to use the Barnes Hut octree approximation and "dynamics" between levels. This is a bad assumption to make though and I certainly don't want to reduce the value of his contribution. 

In any case, this behavior helps me identify a bare bones algorithm for multilevel dynamic graph drawing which identifies the mechanisms (and theory) which are required by default for any implementation. In order to continue, I have instead opted to implement Veldhuizens algorithm first, then develop my own bare bones algorithm (and after, improve upon it). For this though, I have requested aid from my supervisors so I can fully understand the algorithm (there's a lot of mathsy stuff which confuses me a little). 

In the mean time, I am checking over and editing my literature review to put it into some readable format (as opposed to notes pushed together as it is currently). With less than a year, I better get a move on - as the song goes -  "our time is ruuuuuuuunning ooooouuuuut".

Cooling Schedule

Almost all of the literature my work in static graph drawing is based off, uses a cooling schedule to reduce the movement of vertices as a layout is generated. However, there has been little discussion of a cooling schedule in Dynamic Graph Drawing.

A quick recap: the cooling schedule steadily reduces the movement of vertices when given a layout from force directed placement algorithms, in effect, cooling the graph into a good layout. Without such algorithm, vertices would not be cooled, and would remain as a "liquid" - with the ability to move large distances around the placements.

Such techniques are widely used in force directed placement graph drawing approaches for static graphs, but not in dynamic graph drawing. My addition to my literature review has shown that many algorithms in use do not require such techniques as they use hierarchical and/or orthogonal layout techniques, or deal with such small graphs that a cooling schedule is not required (for example, using Eades heuristic would not require a cooling schedule due to the method used to move vertices).

There are some dynamic algorithms which do use cooling schedules however; Lin, Lee and Yen extend the Simulated Annealing FDP approach described by Davidson and Harel (birthplace of cooling schedules), to dynamic graphs, and maintain the same cooling schedule. More importantly, Veldhuizen's work also describes a method of cooling the layout through "damping", shown to be effective at controlling the erratic changes in vertex positions during visualisation.

It is obvious that any FDP orientated approach should use a cooling method, but there has been little investigation as to the loss in efficiency that comes from using one designed for static graphs. As dynamic graphs are ever changing, it would make sense to use this time to improve upon layouts instead of generating a layout once and calling it a day.

Experiments have shown that by resetting the cooling schedule, a graph will build upon the previous layout and improve it. Please see the videos below (YouTube links), which show that resetting the cooling schedule can further improve layout. The last video shows a graph drawing with no cooling schedule, resulting in jerky vertex movements.

Drawing a 20x20 vertex graph, resetting the cooling schedule: http://www.youtube.com/watch?v=FiD1uFQR49U

Drawing a 7x7x7 3D grid, resetting the cooling schedule: http://www.youtube.com/watch?v=VkADKI_FJsk

Drawing the same 7x7x7 3D Grid without a cooling schedule: http://www.youtube.com/watch?v=P5LYL7eG2uk

The effect this will have on larger graphs using the multilevel scheme is unknown, but it is expect to have more of an effect on local structure. Although not a significant point in terms of graph drawing, it is an interesting topic which may have implications at a later date.