NFGD: Neighborhood-Faithful Graph Drawing

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.