Improved force-directed layouts - Graphviz

Techniques for drawing graphs based on force-directed place- ment and virtual physical models have proven surprisingly successful in producing good layouts of undirected graphs. Aspects of symmetry, structure, clustering and reasonable vertex distribution arise from initial, formless clouds ofpoints. However,when nodes must be labeled and point vertices are replaced by non-pointvertices, simple force-directed models produce unreadable drawings,

even for a moderate number of nodes. This paper describes the application of two post-processing techniques that can be applied to any initial vertex layout to produce uncluttered layouts with non-point nodes. 1 Introduction In general, drawing undirected graphs is problematic. The di#0Eculty lies in there being too much freedom. If structure is imposed on the graph, workable tech- niques arise. For example, if the graph is interpreted to have a directed #0Dow, one canemploythe Sugiyama-stylealgorithms#5B25,12#5D.Alternatively,one can suitably restrict the layout style in order to get a handle on the problem. As an example here, we can consider the class of orthogonal layouts, for which a collection of well-developed and analyzed algorithms is available#5B26,27,8#5D. But without us- ing such restrictions, there is, at present, no simple non-heuristic algorithm for e#0Eciently drawing general undirected graphs. The most e#0Bective techniques for handling undirected graphs are based on virtual physical models. These techniques, going back to Eades#5B6#5D and, compu- tationally, to Kruskal#5B17#5D, represent the vertices of a graph as physical objects subject to various forces, natural and unnatural. Some subset of the forces en- codes the edge informationof the graph, typically as an attractive force between the two endpoints of the edge. The object then becomes one of repositioning the nodes in order to minimize the energy of the system or to achieve a stable con#0Cguration vis-a-vis the forces acting on the particles. Standard techniques, such as steepest descent or discrete iteration, can be used to search for the de- sired con#0Cguration,although there is always the possibilityof only #0Cnding a local minimum.Once the #0Cnal node positions are determined, the drawing is typically completed by connecting edge endpoints with line segments. In practice, these layout methods are remarkably good, especially given the naive nature of the algorithms #28cf. #5B18,7#5D#29. The resulting drawings typically cap- ture many symmetries of the graph, while avoiding the expensive computations 2 Marden ldt kg hg ggt Epstein kt Freedman ds Milnor cd Thurston vd Douady Hubard fg Mandelbrot Mumford Conway lat cg Tarjan Cannon crys gcv Almgren Dobkin Chazelle cv Taylor fd Peskin sg Wilks gv dv Fig.1. The e#0Bect of non-point nodes involved in explicitly looking for symmetries#5B19#5D. In addition, these methods identify signi#0Ccant clusters of nodes while producing a reasonable distribution of the nodes. There has been a varietyofwork on this class of algorithms#5B14, 10,4,9,24,2,15,13,3#5D, leading to some quite e#0Ecient algorithmsthat can handle #5Cmedium-sized" graphs. Despite the...

Website: www.graphviz.org | Filesize: -
No of Page(s): 10
Download Improved force-directed layouts - Graphviz.pdf