Una mejora del algoritmo de Bach et al. para dibujos confluentes en visualización de grafos

Fuentes: Further Towards Unambiguous Edge Bundling: Investigating Power-Confluent Drawings for Network Visualization

El artículo parte del algoritmo de Bach et al. [1] para construir dibujos confluentes —una técnica de dibujo de grafos que elimina cruces permitiendo que las aristas se solapen en empalmes suaves, análogos a los cambios de vía en un trazado ferroviario—. Ese algoritmo aprovecha una descomposición en power graph para generar un grafo de encaminamiento auxiliar y, después, interpola los puntos de control con B-splines siguiendo el camino más corto a través de dicho grafo.

Los autores identifican dos problemas no resueltos en el método original. El primero, llamado node split, afecta a cómo se separan los nodos de encaminamiento en uno de entrada y otro de salida para que las B-splines solapen: en grafos no dirigidos existe una ambigüedad sobre qué aristas son entrantes y cuáles salientes, y un particionado incorrecto introduce aristas espurias. El segundo, bautizado short-circuit, ocurre porque las B-splines de grado p se solapan siempre que compartan al menos p puntos de control, lo que puede hacer que ciertas configuraciones del grafo de encaminamiento sugieran visualmente aristas inexistentes, violando la segunda condición de la definición de dibujo confluente.

La solución propuesta modifica el grafo de encaminamiento para conservar la estructura jerárquica de los grupos del power graph, eliminando la ambigüedad del node split y evitando los cortocircuitos. Con esta modificación se garantiza la segunda condición de la definición, aunque no la tercera. Los autores demuestran además que los dibujos que su algoritmo puede producir forman una subclase —los power-confluent drawings— estrictamente contenida en los strict confluent drawings estudiados previamente por Dickerson et al. [2]. El trabajo incluye pseudocódigo, código fuente abierto y una versión mejorada del propio método de construcción del power graph. El texto, firmado por Jonathan X. Zheng, Samraat Pawar y Dan F. M. Goodman (Imperial College London), se enmarca en la visualización de redes y combina teoría de grafos, geometría computacional y diseño de algoritmos.