A Visual Methodology to Assess Spatial Graph Vertex Ordering Algorithms

• Karelia Salinas USP
• Victor Barella USP
• Thales Vieira UFAL
• Luis Gustavo Nonato USP

Resumo

Graph vertex ordering is crucial for various graph-related applications, especially in spatial and urban data analysis where graphs represent real-world locations and their connections. The task is to arrange vertices along a single axis while preserving spatial relationships, but this often results in distortions due to the complexity of spatial data. Existing methods mostly assess ordering quality using a global metric, which may not capture specific use case needs or localized variations. This work proposes a new methodology to visually evaluate and compare vertex ordering techniques on spatial graphs. Two quantitative comparison mechanisms are proposed. Experiments on urban data from various cities demonstrate the methodology's effectiveness in tuning hyperparameters and comparing well-known vertex ordering techniques. The visual approach reveals nuanced spatial patterns that global metrics might miss, providing deeper insights into the behavior of different vertex ordering methods.

Palavras-chave: Visualization, Histograms, Data analysis, Urban areas, Length measurement, Distortion, Spatial databases, Frequency measurement, Complexity theory, Tuning