Same Quality Metrics, Different Graph Drawings - arXiv 2508.15557v1

Oct 29, 2026

Graph drawings visualize relational data, and users’ understanding and performance depend on the quality metrics used to evaluate such drawings. Research practice often assumes that high metric values indicate goodness and that similar metric values imply similar perceived quality. This work challenges those assumptions by transforming existing high-quality graph drawings into arbitrary target shapes while keeping one or more quality metric values almost identical. The results show that advanced quality metrics are needed, because relying on single metrics—or fixed metric combinations—can be confidently misleading.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages19

Reading Time48 min

AccessFree to download

Introduction

Same Quality Metrics, Different Graph Drawings

Related Work

arXiv :2508 . 15557v1 [ cs .CG] 21 Aug 2025 Same Quality Metrics, Different Graph Drawings Simon van Wageningen \# Ñ Utrecht University Department of Information and Computing Sciences, The Netherlands Tamara Mchedlidze \# Ñ Utrecht University Department of Information and Computing Sciences, The Netherlands Alexandru C. Telea \# Ñ Utrecht University Department of Information and Computing Sciences, The Netherlands | | | START X VERT HOR O DINO GRID | | --- | --- | --- | | bar-albert | ST | | ELD CN AR ST-ELD-CN-AR Figure 1 Morphing a graph drawing (START) into six different target shapes (X,VERT,HOR,O,DINO,GRID) while keeping one or more quality metric(s) nearly constant (ST,ELD,CN,AR) . Values for ST,ELD,AR are within ±ϵ = 0 .0025 and within ±ϵ = CN(Γ) ∗ 0.05 for CN, so the morphed drawings have very similar quality to the starting ones. ~~ Abstract ~~ Graph drawings are commonly used to visualize relational data. User understanding and performance are linked to the quality of such drawings, which is measured by quality metrics. The tacit knowledge in the graph drawing community about these quality metrics is that they are not always able to accurately capture the quality of graph drawings. In particular, such metrics may rate drawings with very poor quality as very good. In this work we make this tacit knowledge explicit by showing that we can modify existing graph drawings into arbitrary target shapes while keeping one or more quality metrics almost identical. This supports the claim that more advanced quality metrics are needed to capture the ‘goodness’ of a graph drawing and that we cannot confidently rely on the value of a single (or several) certain quality metrics. 2012 ACM Subject Classification Human-centered computing → Graph drawings Keywords and phrases graph drawing, quality metrics, assumptions, fooling Supplementary Material [https://github.com/simonvw95/Same-Quality-Metric--Different-Graph](https://github.com/simonvw95/Same-Quality-Metric--Different-Graph)Drawings 1 Introduction Relational data is typically visualized using node-link diagrams, commonly known as graph drawings (GD) . High-quality graph drawings are key to user understanding and performance [31] . In turn, such quality is measured by various so-called quality metrics (QM) [30] . Ata high level QMs capture two different aspects of the goodness of a GD: 1 . how readable the elements of the drawing are, e.g., few crossings, few node overlaps – we call these readability metrics; and 2 . how well the graph structure is represented by the drawing – faithfulness 2 Same Quality Metrics, Different Graph Drawings metrics. For instance, nodes lie at distances similar to their graph theoretical distances (measured by stress) or clusters are clearly depicted [28] Quality metrics tend to correlate – often by design – with the aesthetic preferences of users [18, 31] and task performance [29] . As such, GD algorithms aim to (in)directly optimize them in order to produce pleasing drawings. For instance, spring-based techniques like Fruchterman-Reingold [15] and ForceAtlas2 [20] use forces on their nodes (and edges) in various ways, leading to drawings with ‘good’ scores on most GD quality metrics. Other techniques like Stress Majorization [16], Stress-Plus-X [11], DeepGD [36], SGD2 [1], and Core-GD [17] directly optimize one or more metrics to produce aesthetically pleasing drawings. Two underlying and often implicit assumptions on quality metrics are that a ‘high’ value indicates a ‘good’ drawing; and that drawings of the same graph with similar metric values have similar quality. It is, however, widely known by Graph Drawing researchers, and has been exemplified multiple times by the Graph Drawing live challenge [12], that these assumptions do not always hold. In particular, over the years, GD challenge participants have presented drawings with very high QMs values that had an obfuscating appearance and did not r

FAQs

What core assumptions does the paper question about graph drawing quality metrics?

It questions the assumptions that high metric values always indicate good drawings and that drawings with similar metric values must have similar quality.

How does the paper modify drawings while preserving quality metric values?

It morphs existing graph drawings into arbitrary target shapes using a simulated annealing process while keeping one or more given quality metric values relatively fixed.

What does the paper demonstrate about fooling both readability and faithfulness metrics?

It shows that quality metrics can be fooled so that the graph structure becomes obfuscated, including for faithfulness-related metrics such as stress, not only readability metrics.

Oct 29, 2026

Upload by McGucket