Drawing graphs with nonuniform nodes using potential fields

Chun-Cheng Lin, Hsu Chun Yen*, Jen-Hui Chuang

*Corresponding author for this work

Research output: Contribution to journalArticle

8 Scopus citations

Abstract

Graphs with nonuniform nodes arise naturally in many real-world applications. Although graph drawing has been a very active research in the computer science community during the past decade, most of the graph drawing algorithms developed thus far have been designed for graphs whose nodes are represented as single points. As a result, it is of importance to develop drawing methods for graphs whose nodes are of different sizes and shapes, in order to meet the need of real-world applications. To this end, a potential field approach, coupled with an idea commonly found in force-directed methods, is proposed in this paper for drawing graphs with nonuniform nodes in 2-D and 3-D. In our framework, nonuniform nodes are uniformly charged, while edges are modelled by springs. Using certain techniques developed in the field of potential-based path planning, we are able to find analytically tractable procedures for computing the repulsive force and torque of a node in the potential field induced by the remaining nodes. The crucial feature of our approach is that the rotation of every nonuniform node and the multiple edges between two nonuniform nodes are taken into account. In comparison with the existing algorithms found in the literature, our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of moderate-sized graphs in 2-D and 3-D can be produced reasonably efficiently. That is, our approach is suitable for moderate-sized interactive graphs or larger-sized static graphs. Furthermore, to illustrate the usefulness of our new drawing method for graphs with zero-sized nodes, we give an application to the visualization of hierarchical clustered graphs, for which our method offers a very efficient solution.

Original languageEnglish
Pages (from-to)385-402
Number of pages18
JournalJournal of Visual Languages and Computing
Volume20
Issue number6
DOIs
StatePublished - 1 Dec 2009

Keywords

  • Graph drawing
  • Potential field

Fingerprint Dive into the research topics of 'Drawing graphs with nonuniform nodes using potential fields'. Together they form a unique fingerprint.

  • Cite this