Recursive Space Decompositions in Force-Directed Graph Drawing Algorithms

Pulo, K.J.

Force-directed graph drawing algorithms are a popular method of drawing graphs, but poor scalability makes them unsuitable for drawing large graphs. The FADE paradigm uses the proximity information in recursive space decompositions to address this problem and that of high visual complexity. The FADE paradigm has been presented with a simple and common recursive space decomposition known as the quadtree. However, quadtrees have the disadvantage of not being robust with respect to small perturbations and some transformations of the input data, and this can adversely affect the resultant graph drawing. This paper investigates the FADE paradigm using an alternative recursive space decomposition known as the recursive voronoi diagram, which avoids some of the problems found in quadtrees at an additional time complexity cost. Preliminary results with random graphs and graphs in the domain of software engineering are presented and suggest that using better recursive space decompositions has promise, but the additional computational effort may not be easily justified.

Cite as: Pulo, K.J. (2001). Recursive Space Decompositions in Force-Directed Graph Drawing Algorithms. In Proc. Australian Symposium on Information Visualisation, (invis.au 2001), Sydney, Australia. CRPIT, 9. Eades, P. and Pattison, T., Eds. ACS. 95-102.

(from crpit.com) (local if available)