Forces of Nature
Alan Creek
Department of Computer Science
University of Canterbury
Abstract
Many systems in the modern world are readily represented as graphs; with nodes representing objects within the system, and edges the relationships between them. The effectiveness of visualisations of complex systems is often dependent on the layout of their graphs; a good layout can provide ready understanding of complexity, while a poor layout does nothing to aid comprehension and can even obscure information. We examine the use of force directed placement (FDP) as an algorithm for automatically laying out connected graphs and introduce ANGLE, a software tool for experimentation with graph layout. FDP assigns properties to nodes and edges analogous with real world objects; principally treating edges as springs and nodes as bodies that are mutually repellent. Iterating over the graph and positioning the nodes according to the notional forces upon them provides a means to arrive at a layout. Previous work has focused primarily on two dimensional layouts with various force models. We tackle the extension into three dimensions and propose a new force model that produces a more reliable quality of layout in a shorter time than earlier models. In addition we look at the problem of terminating layout algorithms at an appropriate time, and examine several means of terminating algorithms when a suitable end result has been achieved.