Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title Downloads

Graph Visualization

Yifan Hu
Organization: Wolfram Research, Inc.

2004 Wolfram Technology Conference
Conference location

Champaign IL

Graphs are often used to encapsulate the relationship between objects. Graph drawing enables visualization of such relationships.

The usefulness of this visual representation is dependent on whether the drawing is aesthetic. While there are no strict criteria for aesthetics of a drawing, it is generally agreed, for example, that such a drawing has minimal edge crossings, with vertices evenly distributed in the space, and with symmetry that may exist in the graph depicted. This problem has been studied extensively in the literature (e.g., Battista et al, 1999}), and many approaches were proposed. In this talk we concentrate on drawing undirected graphs with straight-line edges, using methods including force-directed methods (e.g., Fruchterman and Reigold, 1991). We propose a graph drawing algorithm that is both efficient and of high quality. This algorithm combines a multilevel approach which effectively overcomes local minimums, with octree technique which approximates short and long range force efficiently. Our numerical results show that the algorithm is competitive in speed to Walshaw's (Walshaw, 2003) highly efficient multilevel graph drawing algorithm, yet gives better drawing for some of the difficult problems. The algorithms will be illustrated using examples, including large graphs of tens of thousands of vertices, in real time.

*Mathematics > Discrete Mathematics > Graph Theory

TechConf_Conference_2004_Talk.zip (11.6 MB) - Presentation notebook