Drawing Graphs with Nonuniform Nodes Using Potential Fields

Chuang, Jen-Hui and Lin, Chun-Cheng and Yen, Hsu-Chun (2004) Drawing Graphs with Nonuniform Nodes Using Potential Fields. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 460-465 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_43).

Full text not available from this repository.


A potential field approach, coupled with 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 or nonuniformly 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. Our experimental results suggest this new approach to be promising, as drawings of good quality for a variety of graphs in 2-D and 3-D can be produced efficiently.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_43
Classifications:P Styles > P.060 3D
M Methods > M.400 Force-directed / Energy-based
ID Code:475

Repository Staff Only: item control page


D. Harel and Y. Koren. Drawing graphs with non-uniform vertices. Proc. of Working Conference on Advanced Visual Interfaces (AVI '02), pp. 157-166, ACM Press, 2002.

P. Eades. A heuristic for graph drawing. Congress Numerantium, 42, pp. 149-160, 1984.

J.-H. Chuang and N. Ahuja. An analytically tractable potential field model of free space and its application in obstacle avoidance. IEEE Transactions on System, Man, and Cybernetics - Part B: Cybernetics, Vol. 28, No. 5, pp. 729-736, Oct, 1998.

J.-H. Chuang. Potential-based modeling of three-dimensional workspace for obstacle avoidance. IEEE Trans. Robotics and Automation, Vol. 14, No. 5, pp. 778-785, Oct. 1998.

P. Eades and M. L. Huang. Navigating clustered graphs using force-directed methods. Journal of Graph Algorithm and Applications, Vol. 4, No. 3, pp. 157-181, 2000.

M. Huang, P. Eades and J. Wang. On-line animated visualization of huge graphs using a modified spring algorithm. Journal of Visual Languages and Computing, pp. 623-345, 1998.