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.