A new force-directed graph drawing method based on edge-edge repulsion

Chun-Cheng Lin, Hsu Chun Yen*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

The conventional force-directed methods for drawing undirected graphs are based on either vertex-vertex repulsion or vertex-edge repulsion. In this paper, 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 according to spring forces and the repulsive forces, derived from potential fields, among edges. Different from the previous methods, our new framework has the advantage of overcoming the problem of zero angular resolution, guaranteeing 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.

Original languageEnglish
Pages (from-to)29-42
Number of pages14
JournalJournal of Visual Languages and Computing
Volume23
Issue number1
DOIs
StatePublished - 1 Feb 2012

Keywords

  • Angular resolution
  • Force-directed method
  • Potential field

Fingerprint Dive into the research topics of 'A new force-directed graph drawing method based on edge-edge repulsion'. Together they form a unique fingerprint.

Cite this