Another paper, luck requested!

Another rather late post to add to the collection of sparser and sparser updates.

So what have I been up to? Another conference paper! This time for the prestigious Graph Drawing conference, which is a rather big and intimidating deal. Unfortunately, the work submitted is only an addition and not the dynamic stuff we've been working on - but I guess that's what happens when you leave the big bits to the last minute.

So the work - leaf processing! We have successfully proven that processing edges in a graph reduces runtime due to the smaller graph size, and when using MGF approximation, reduced depth of the coarsening scheme (resulting in less approximations). We also suggest a simple Leaf Placement Algorithm for the layout of these vertices without the use of iteration (no FDP for you!). Unfortunately the LPA does increase the number of edge crossings somewhat, as the placement only accounts for the centre of mass and not for other nearby vertices, but this can be changed by implementing different algorithms. The concept is that we can control the layout of leafy vertices with ease - and by doing some simple preprocessing, can reduce the runtime required to generate layout for leafy graphs.

For more information you'll have to wait and see if the paper is accepted (mostly because I dont want to jinx it).

Anyway, moving on, what's next? The Dynamic stuff!! hurrah! We have the changes and operations currently implements (may not be optimised but they do their duty) and the framework for altering the coarsening scheme after these changes exists (but has not been tested so who knows what bugs are waiting for me there). More importantly, the cooling schedule mentioned in the previous post is implemented, so now its time to port that to the multilevel algorithms, so we can speed up the drawing.

A plan has been developed on scraps of paper scattered across the 5 corners of the world, and the code has been prepared in a special ceremony - so I guess now its down to me. Let us begin. I will update again in the future with a progress report. So luck be with me!