Algorithms for Cluster Busting in Anchored Graph Drawing

Abstract

Given a graph G and a drawing or layout of G, it is sometimes desirable to alter or adjust the layout. The challenging aspect of designing layout adjustment algorithms is to maintain a user’s mental picture of the original layout. We present a new approach to layout adjustment called cluster busting in anchored graph drawing. We then give two algorithms as examples of this approach. The goals of cluster busting in anchored graph drawing are to more evenly distribute the nodes of the graph in a drawing window while maintaining the user’s mental picture of the original drawing. We present simple and ecient iterative heuristics to accomplish these goals. We formally dene some measures of distribution and similarity and give empirical results based on these measures to quantify our methods. The theoretical analysis of our heuristics presents a formidable challenge, thus justifying our empirical analysis.