A fast successive over-relaxation algorithm for force-directed network graph drawing

DOI10.1007/S11432-011-4208-9zbMATH Open1245.68148arXiv1711.01228OpenAlexW3098135377MaRDI QIDQ439759FDOQ439759

Authors: Yongxian Wang, Zhenghua Wang 

Publication date: 17 August 2012

Published in: Science China Information Sciences (Search for Journal in Brave)

Abstract: Force-directed approach is one of the most widely used methods in graph drawing research. There are two main problems with the traditional force-directed algorithms. First, there is no mature theory to ensure the convergence of iteration sequence used in the algorithm and further, it is hard to estimate the rate of convergence even if the convergence is satisfied. Second, the running time cost is increased intolerablely in drawing large- scale graphs, and therefore the advantages of the force-directed approach are limited in practice. This paper is focused on these problems and presents a sufficient condition for ensuring the convergence of iterations. We then develop a practical heuristic algorithm for speeding up the iteration in force-directed approach using a successive over-relaxation (SOR) strategy. The results of computational tests on the several benchmark graph datasets used widely in graph drawing research show that our algorithm can dramatically improve the performance of force-directed approach by decreasing both the number of iterations and running time, and is 1.5 times faster than the latter on average.

Full work available at URL: https://arxiv.org/abs/1711.01228

Recommendations

• Faster force-directed graph drawing with the well-separated pair decomposition
• Graph Drawing
• Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition
• scientific article; zbMATH DE number 2080097
• A Multilevel Algorithm for Force-Directed Graph-Drawing

zbMATH Keywords

graph drawingforce-directed algorithmgraph layoutsuccessive over-relaxation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis
• Nonmetric multidimensional scaling. A numerical method
• Convergence of the majorization method for multidimensional scaling
• Iterative Solution of Nonlinear Equations in Several Variables
• Title not available (Why is that?)
• Integrating Edge Routing into Force-Directed Layout
• Drawing graphs. Methods and models
• An algorithm for drawing general undirected graphs
• Three-dimensional graph drawing
• Constrained graph layout by stress majorization and gradient projection
• Graph layout techniques and multidimensional data analysis
• Hybrid layout algorithm based on skeleton subgraph
• Constrained Stress Majorization Using Diagonally Scaled Gradient Projection
• Graph Drawing

Cited In (3)

• Faster force-directed graph drawing with the well-separated pair decomposition
• Faster Force-Directed Graph Drawing with the Well-Separated Pair Decomposition
• Data-driven graph drawing techniques with applications for conveyor systems

This page was built for publication: A fast successive over-relaxation algorithm for force-directed network graph drawing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439759)