NFGD: Neighborhood-Faithful Graph Drawing

Thumbnail Image
Files
evs20251090.pdf (2.75 MB)
Date
2025
Authors
Fan, Yuming
Hong, Seok-Hee
Meidiana, Amyra
Journal Title
Journal ISSN
Volume Title
Publisher
The Eurographics Association
Abstract
Neighborhood faithfulness metrics measure how faithfully the ground truth neighbors of vertices in a graph G are represented as the geometric neighbors of vertices in a drawing D of G. In this paper, we present NFGD, a post-processing algorithm for optimizing the neighborhood faithfulness of graph drawings. Experiments demonstrate the effectiveness of NFGD for computing neighbor-faithful drawings, on average 320% improvement over the popular graph drawing algorithms: 425% over Stress Majorization (SM) and 215% over force-directed algorithm Fruchterman-Reingold (FR). In particular, for scale-free graphs, NFGD-SM achieves 776% improvement over SM and NFGD-FR obtains 597% improvement over FR.
Description

CCS Concepts: Human-centered computing → Graph drawings

        
@inproceedings{
10.2312:evs.20251090
,
booktitle = {
EuroVis 2025 - Short Papers
},
editor = {
El-Assady, Mennatallah
 and 
Ottley, Alvitta
 and 
Tominski, Christian
},
title = {{
NFGD: Neighborhood-Faithful Graph Drawing
}},
author = {
Fan, Yuming
 and 
Hong, Seok-Hee
 and 
Meidiana, Amyra
},
year = {
2025
},
publisher = {
The Eurographics Association
},
ISBN = {
978-3-03868-282-0
},
DOI = {
10.2312/evs.20251090
}
}
Citation
URI
https://doi.org/10.2312/evs.20251090
 https://diglib.eg.org/handle/10.2312/evs20251090
Collections
EuroVisShort2025