A New Force-Directed Graph Drawing Method Based on Edge

A New Force-Directed Graph Drawing Method Based on Edge-Edge RepulsionI Chun-Cheng Lina, Hsu-Chun Yen∗,b aDept. of Industrial Engineering and Management, National Chiao Tung University, Hsinchu, Taiwan, R.O.C. bDept. of Electrical Engineering, National Taiwan University, Taipei, Taiwan, R.O.C. Abstract The conventional force-directed methods for drawing undirected graphs are based on either vertex-vertex repulsion or vertex-edge repulsion. In this pa- per, we propose a new force-directed method based on edge-edge repulsion to draw graphs. In our framework, edges are modelled as charged

springs, and a final drawing can be generated by adjusting positions of vertices accord- ing to spring forces and the repulsive forces, derived from potential elds, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guar- anteeing the absence of any overlapping of edges incident to the common vertex. Given graph layouts probably generated by previous algorithms as the inputs to our algorithm, experimental results reveal that our approach produces promising drawings not only preserving the original properties of a high degree of symmetry and uniform edge length, but also preventing zero angular resolution and usually having larger average angular resolution. However, it should be noted that exhibiting a higher degree of symmetry and larger average angular resolution does not come without a price, as the new approach might result in the increase in undesirable overlapping of vertices as some of our experimental results indicate. To ease the problem of node overlapping, we also consider a hybrid approach which takes into account both edge-edge and vertex-vertex repulsive forces in drawing a graph. Key words: Force-directed method, potential field, angular resolution IA preliminary version of this work was presented at the 9th International Conference on Information Visualisation, July 6-8, 2005, London, UK. Corresponding author. E-mail: yen@cc.ee.ntu.edu.tw Preprint submitted to a journal December 20, 2011 1. Introduction As graphs are known to be one of the most important abstract models in various scientific and engineering areas, graph drawing (or information visualization in a broader sense) has naturally emerged as a fast growing research topic in computer science. Among various graph drawing techniques reported in the literature, the so-called force-directed methods (see, e.g., [1, 3, 4, 7, 11, 13, 15, 18, 25, 28])) have received much attention and have become very popular for drawing general, undirected graphs. In such a framework, a graph is viewed as a system of particles with forces acting between the particles, and then a good configuration or drawing of the particles could be generated with locally minimal energy, i.e., the sum of the forces on each particle is zero. Generally speaking, the notions of repulsions in the setting of conven- tional force-directed methods fall into two categories, namely, vertex-vertex repulsion and vertex-edge repulsion. First, Eades [4] presented a vertex-vertex repulsion model in which vertices are replaced with charged steel rings and edges with springs to form...

Website: web.it.nctu.edu.tw | Filesize: -
No of Page(s): 29
Download A New Force-Directed Graph Drawing Method Based on Edge-Edge ....pdf