Visually Comparing Graph Vertex Ordering Algorithms through Geometrical and Topological Approaches

Abstract

Graph vertex ordering is a resource widely employed in spatial data analysis, particularly in the urban analytics context, where street graphs are frequently used as spatial discretization for modeling and simulation. Vertex ordering is also important for visualization purposes, as many methods require the vertices to be arranged and displayed in a well-defined order to enable the visual identification of non-trivial patterns. The primary goal of vertex ordering methods is to find an ordering that preserves neighborhood relations. However, the structural complexity of graphs employed in real-world applications leads to unavoidable distortions in the ordering process. Therefore, comparing different vertex ordering methods is fundamental to enable effective analysis and selection of the most appropriate method in each application. Although several metrics have been proposed to assess spatial vertex ordering, they typically focus on measuring the quality of the ordering globally. Global ordering assessment does not enable the analysis and identification of locations where distortions are more pronounced, hampering the analytical process. Visual evaluation of the vertex ordering mechanisms is particularly valuable in this context, as it allows analysts to distinguish between methods based on their performance within a single visualization, assess distortions, identify regions with anomalous behavior, and, in urban contexts, explain spatial inconsistencies in the ordering. This work introduces a visualization-assisted tool to assess vertex ordering techniques, having urban analytics as the application focus. Specifically, we evaluate geometric and topological vertex ordering approaches using urban street graphs as the basis for comparisons. The visual tool builds upon existing and newly proposed metrics, which are validated through experiments on urban data from multiple cities, demonstrating that the proposed methodology is effective in assisting users in selecting a suitable vertex ordering technique, fine-tuning hyperparameters, and identifying regions with high ordering distortions.