A multilevel algorithm for force-directed graph drawing

We describe a heuristic method for drawing graphs which uses a multilevel technique combined with a force-directed placement algorithm. The multilevel process groups vertices to form clusters, uses the clusters to define a new graph and is repeated until the graph size falls below some threshold. The coarsest graph is then given an initial layout and the layout is successively refined on all the graphs starting with the coarsest and ending with the original. In this way the multilevel algorithm both accelerates and gives a more global quality to the force- directed placement. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on a number of examples ranging from 500 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 30 seconds for a 10,000 vertex graph to around 10 minutes for the largest graph. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

A multilevel algorithm for force-directed graph-drawing

We describe a heuristic method for drawing graphs which uses a multilevel framework combined with a force-directed placement algorithm. The multilevel technique matches and coalesces pairs of adjacent vertices to define a new graph and is repeated recursively to create a hierarchy of increasingly coarse graphs, G0, G1, …, GL. The coarsest graph, GL, is then given an initial layout and the layout is refined and extended to all the graphs starting with the coarsest and ending with the original. At each successive change of level, l, the initial layout for Gl is taken from its coarser and smaller child graph, Gl+1, and refined using force-directed placement. In this way the multilevel framework both accelerates and appears to give a more global quality to the drawing. The algorithm can compute both 2 & 3 dimensional layouts and we demonstrate it on examples ranging in size from 10 to 225,000 vertices. It is also very fast and can compute a 2D layout of a sparse graph in around 12 seconds for a 10,000 vertex graph to around 5-7 minutes for the largest graphs. This is an order of magnitude faster than recent implementations of force-directed placement algorithms.

Public sector pay in the UK: has the historic pattern of public/private sector pay movements been broken?

The historic pattern of public sector pay movements in the UK has been counter-cyclical with private sector pay growth. Periods of relative decline in public sector pay against private sector movements have been followed by periods of ‘catch-up’ as Government controls are eased to remedy skill shortages or deal with industrial unrest among public servants. Public sector ‘catch up’ increases have therefore come at awkward times for Government, often coinciding with economic downturn in the private sector (Trinder 1994, White 1996, Bach 2002). Several such epochs of public sector pay policy can be identified since the 1970s. The question is whether the current limits on public sector pay being imposed by the UK Government fit this historic pattern or whether the pattern has been broken and, if so, how and why? This paper takes a historical approach in considering the context to public sector pay determination in the UK. In particular the paper seeks to review the period since Labour came into office (White and Hatchett 2003) and the various pay ‘modernisation’ exercises that have been in process over the last decade (White 2004). The paper draws on national statistics on public sector employment and pay levels to chart changes in public sector pay policy and draws on secondary literature to consider both Government policy intentions and the impact of these policies for public servants.