Primitive Coarsening

Primitive Coarsening - identifying primitive graph layouts during the coarsening phase, so to avoid any further coarsening deemed unnecessary and wasteful, and to provide expected positions to vertices.

Having presented my ideas and preliminary results to my primary supervisor, we discussed  a long standing topic in my research - how to deal with graphs when they are coarsened to a primitive graph type such as a trail (chain/path/thing), ring or star of connected vertices. Previously, our implementation of the multilevel scheme has either ignored these and continued to coarsen to two vertices - or if the diffference between levels is less than some tolerance (normally 1 vertex), stop coarsening.

Trailing (new name pending) and Multi-matching has been shown to decrease runtime, with trailing being the more appropriate method (Multi-matching requires a matching number, and each graph may run better or worse with matching numbers, which have so far been unpredictable - should put some results on here soon I guess). Having shown that Trailing works so far, and copes with graphs when coarsened to a trail, we look at the star and ring primitives.

So some some definitions:

• Trail/Chain/Path - two vertices with only 1 adjacent vertex (the ends), and all other vertices between having 2 adjacent vertices.
• Star - one vertex (the center) having V-1 adjacent vertices, and V-1 vertices have 1 adjacent vertex.
• Ring - every vertex having 2 adjacent vertices.

As these structures have a known layout, FDP is unnecessary. The layout can be computed quickly and applied to this level, providing the graph with an "initial layout". This is immediately passed to the next finest graph and does not require refinement.

So far, trailing has providing useful as a preprocessing for the coarsening phases, and results in large reductions in runtime for Add20 and Add32, with some small changes to other more regular structured graphs. Quality, on average, has some small improvement across the board, however, the range makes it rather unreliable - so we need some further investigation on this.

Stopping coarsening when a primitive structure is found further decreases this runtime; as an example, Add20 was previously 10seconds with MGF, this was decreased to 4.7 seconds with Trailing, and further decreased to 3.6seconds with the introduction of Primitive Identification/Coarsening. This is still slower than some of the methods used by Hu, but is a vast improvement on the multilevel runtimes.

Next, I have intention to try an alternate (or additonal) preprocessing method which identifies small star structures in a graph (which may be connected to other star structures), and coarsen those to simplify a graph when trails to not exist but when vertices loosely connected do.

For now, there is a lot of clearing up to do regarding the work and theory, and many many results to collect, analyse and write up. I shall update again and put everything into a less erratic form in the future. Back to work for me, have a good weekend!