EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Visually Comparing Graph Vertex Ordering Algorithms through Geometrical and Topological Approaches

Karelia Vilca Salinas, Victor Barella, Thales Vieira, Luis Gustavo Nonato

Journal of the Brazilian Computer Society · 16.03.2026 · 32 (1) · 363-373

DOI: 10.5753/jbcs.2026.5851 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of the Brazilian Computer Society, online erschienen am 16.03.2026. Verfasst von Karelia Vilca Salinas und 3 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Salinas, K. V., Barella, V., Vieira, T., & Nonato, L. G. (2026). Visually Comparing Graph Vertex Ordering Algorithms through Geometrical and Topological Approaches. Journal of the Brazilian Computer Society, 32(1), 363-373. https://doi.org/10.5753/jbcs.2026.5851

Vancouver

Salinas KV, Barella V, Vieira T, Nonato LG. Visually Comparing Graph Vertex Ordering Algorithms through Geometrical and Topological Approaches. Journal of the Brazilian Computer Society. 2026;32(1):363-373. doi:10.5753/jbcs.2026.5851

BibTeX
@article{Salinas2026,
  author = {Salinas, Karelia Vilca and Barella, Victor and Vieira, Thales and Nonato, Luis Gustavo},
  title = {Visually Comparing Graph Vertex Ordering Algorithms through Geometrical and Topological Approaches},
  journal = {Journal of the Brazilian Computer Society},
  year = {2026},
  volume = {32},
  number = {1},
  pages = {363--373},
  doi = {10.5753/jbcs.2026.5851}
}
Kostenlos starten →