Publicación

Tipo de publicación: Artículos científicos (Publicados en revistas de divulgación o científicas)

Título del artículo: Crossing edge minimization in radial outerplanar layered graphs using segment paths

Registrado por: Journal of Optimization Methods & Software

Año de publicación: 2023

Resumen: Crossing minimization is a natural problem in graph drawing, which
consists of drawing it in the plane with a minimum number of crossings on the edges. We present an algorithm to minimize the crossing
edges in radial layered graphs. The algorithm determines the optimal location of nodes in their corresponding circle layer and consists
of two phases. In the first phase, a counterclockwise rotation of concentric circles is performed; in the next phase, edges are converted
into segment paths. Unlike other algorithms with circular drawings,
our algorithm does not require the insertion or removal of nodes
and edges; only rotation and path construction operations are utilized. Two versions of the algorithm were created; the exhaustive
version tests all the possible paths, while the random version tests
a few number of paths. The goal is to minimize the crossing edges
to obtain a clear visualization using three criteria: rotation, crossing
edge detection and segment path construction. The algorithm has
been successfully implemented in 30 instances of graphs with 20,
35 and 50 layers, where crossings are minimized in 86–93%, 93–96%
and 95–97%, respectively

Editorial:

Número de páginas:

Autor(es): Francisco Madera-Ramírez, Joel Antonio Trejo-Sánchez, José López-Martínez, and Jorge Ríos-Martínez

Campo: Computación

Disciplina: Ciencias de la Computación

Subdisciplina: Teoría de Grafos

Número de registro: https://doi.org/10.1080/10556788.2023.2205646