標題: Drawing graphs with nonuniform nodes using potential fields
作者: Lin, Chun-Cheng
Yen, Hsu-Chun
Chuang, Jen-Hui
資訊工程學系
Department of Computer Science
關鍵字: Graph drawing;Potential field
公開日期: 1-Dec-2009
摘要: 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. (C) 2009 Elsevier Ltd. All rights reserved.
URI: http://dx.doi.org/10.1016/j.jvlc.2009.04.006
http://hdl.handle.net/11536/6398
ISSN: 1045-926X
DOI: 10.1016/j.jvlc.2009.04.006
期刊: JOURNAL OF VISUAL LANGUAGES AND COMPUTING
Volume: 20
Issue: 6
起始頁: 385
結束頁: 402
Appears in Collections:Articles


Files in This Item:

  1. 000271443900003.pdf

If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.