Neighborhood beautification: Graph layout through message passing. (February 2018)

• Record Type: Journal Article
• Authors: Galán, Severino F.; Mengshoel, Ole J.
• Is Part Of: Journal of visual languages & computing. Volume 44(2018)
• Page Start: 72
• Page End: 88
• Publication Date: 2018-02
• Subjects: Graph drawing -- Aesthetic graph layout -- Neighborhood interaction -- Message passing; Visual programming languages (Computer science) -- Periodicals; Visual programming (Computer science) -- Periodicals; Programming languages (Electronic computers) -- Semantics -- Periodicals; Langages de programmation visuelle -- Périodiques; Programmation visuelle -- Périodiques; Langages de programmation -- Sémantique -- Périodiques; Programming languages (Electronic computers) -- Semantics; Visual programming (Computer science); Visual programming languages (Computer science); Periodicals; Electronic journals; 005
• DOI: 10.1016/j.jvlc.2017.11.008
• Languages: English
• ISSNs: 1045-926X

Abstract

Abstract: Graph layout algorithms are used to compute aesthetic and useful visualizations of graphs. In general, for graphs with up to a few hundred nodes, force-directed layout algorithms produce good layouts. Unfortunately, for larger graphs, they often get stuck at local minima and have high computational complexity. In this paper, we introduce a novel message passing technique for graph layout. The key idea of our message passing technique is that an aesthetic layout can be obtained if each node independently suggests aesthetic placements of its neighbors. In other words, every node sends messages to its neighbors, indicating new and better positions for them. As a result, the new technique, which we call Neighborhood Beautification, provides a new perspective that turns out to give a useful trade-off between the excellent layout quality reached by force-directed methods and the fast runtime achieved by algebraic methods. Neighborhood Beautification reduces, in many cases, the computational cost of force-directed algorithms, since only interactions between neighboring nodes are considered. Experimentally, we show that Neighborhood Beautification produces high-quality layouts for grid-like graphs but is outperformed by force-directed algorithms in the case of more complex graphs.