Neighborhood beautification: Graph layout through message passing. (February 2018)
- Record Type:
- Journal Article
- Title:
- Neighborhood beautification: Graph layout through message passing. (February 2018)
- Main Title:
- Neighborhood beautification: Graph layout through message passing
- Authors:
- Galán, Severino F.
Mengshoel, Ole J. - 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.
- Is Part Of:
- Journal of visual languages & computing. Volume 44(2018)
- Journal:
- Journal of visual languages & computing
- Issue:
- Volume 44(2018)
- Issue Display:
- Volume 44, Issue 2018 (2018)
- Year:
- 2018
- Volume:
- 44
- Issue:
- 2018
- Issue Sort Value:
- 2018-0044-2018-0000
- 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 - Journal URLs:
- http://www.sciencedirect.com/science/journal/1045926X ↗
http://www.elsevier.com/journals ↗ - DOI:
- 10.1016/j.jvlc.2017.11.008 ↗
- Languages:
- English
- ISSNs:
- 1045-926X
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 5072.495200
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 6375.xml