Overlap-free labeling of clustered networks based on Voronoi tessellation. (February 2018)

• Record Type: Journal Article
• Authors: Wu, Hsiang-Yun; Takahashi, Shigeo; Ishida, Rie
• Is Part Of: Journal of visual languages & computing. Volume 44(2018)
• Page Start: 106
• Page End: 119
• Publication Date: 2018-02
• Subjects: Adaptive layout blending -- Force-directed layouts -- Centroidal Voronoi tessellation -- Chebyshev distance -- Centrality-based clustering; 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.09.008
• Languages: English
• ISSNs: 1045-926X

Abstract

Abstract: Properly drawing clustered networks significantly improves the visual readability of the meaningful structures hidden behind the associated abstract relationships. Nonetheless, we often degrade the visual quality of such clustered graphs when we try to annotate the network nodes with text labels due to their unwanted mutual overlap. In this paper, we present an approach for aesthetically sparing labeling space around nodes of clustered networks by introducing a space partitioning technique. The key idea of our approach is to adaptively blend an aesthetic network layout based on conventional criteria with that obtained through centroidal Voronoi tessellation. Our technical contribution lies in choosing a specific distance metric in order to respect the aspect ratios of rectangular labels, together with a new scheme for adaptively exploring the proper balance between the two network layouts around each node. Centrality-based clustering is also incorporated into our approach in order to elucidate the underlying hierarchical structure embedded in the given network data, which also allows for the manual design of its overall layout according to visual requirements and preferences. The accompanying experimental results demonstrate that our approach can effectively mitigate visual clutter caused by the label overlaps in several important types of networks.