Visual Computing

University of Konstanz
IEEE Transactions on Visualization and Computer Graphics, to appear

Taurus: Towards A Unified Force Representation and Universal Solver for Graph Layout

M. Xue, Z. Wang, F. Zhong, Y. Wang, O. Deussen, Y. Wang

Abstract

Over the past few decades, a large number of graph layout techniques have been proposed for visualizing graphs from various domains. In this paper, we present a general framework, Taurus, for unifying popular techniques such as the spring- electrical model, stress model, and maxent-stress model. It is based on a unified force representation, which formulates most existing techniques as a combination of quotient-based forces that combine power functions of graph-theoretical and Euclidean distances. This representation enables us to compare the strengths and weaknesses of existing techniques, while facilitating the development of new methods. Based on this, we propose a new balanced stress model (BSM) that is able to layout graphs in superior quality. In addition, we introduce a universal augmented stochastic gradient descent (SGD) optimizer that efficiently finds proper solutions for all layout techniques. To demonstrate the power of our framework, we conduct a comprehensive evaluation of existing techniques on a large number of synthetic and real graphs. We release an open-source package, which facilitates easy comparison of different graph layout methods for any graph input as well as effectively creating customized graph layout techniques.

BibTeX

@Article{Xue2022Taurus,
  author  = {Mingliang Xue, Zhi Wang, Fahai Zhong, Yong Wang, Oliver Deussen, Yunhai Wang},
  journal = {IEEE Transactions on Visualization and Computer Graphics (Proc. Vis 2022) , to appear},
  title   = {Taurus: Towards A Unified Force Representation and Universal Solver for Graph Layout},
  year    = {2022},
}