Aplicaciones del criterio de planaridad de Mac Lane en algoritmos paralelos

Abstract

[en] In this work, we demonstrate Mac Lane's planarity criterion [16] (1937) and implement two parallel algorithms based on it, following article [14] (Ja' Ja' and Simon, 1982). The first algorithm determines whether a graph $G = (V, E)$ is planar, and the second, initially proposed in [20] (Tutte, 1963), provides a barycentric embedding of a triconnected graph if it is planar. Both algorithms run in $O(\log^{2}(|V|))$ steps using $O(|V|^{6})$ processors, which improves the execution time of sequential planarity criteria that require $O(|V|)$ steps. Our implementation does not reach this complexity bound because it does not apply parallelization, but it does verify the correctness of the algorithms.

[ca] En este trabajo demostramos el criterio de planaridad de Mac Lane [16] (1937) e implementamos dos algoritmos paralelos que lo aplican basados en el artículo [14] (Ja' Ja' y Simon, 1982). El primer algoritmo determina si un grafo $G = (V, E)$ es planar y el segundo, propuesto inicialmente en [20] (Tutte, 1963), da un encaje baricéntrico de un grafo triconexo si es planar. Ambos algoritmos se ejecutan en $O(\log^{2}(|V|))$ pasos usando $O(|V|^{6})$ procesadores, lo que mejora el tiempo de ejecución de criterios secuenciales de planaridad que utilizan $O(|V|)$ pasos. Nuestra implementación no alcanza esta cota de complejidad porque no aplica paralelización, pero sí verifica la corrección de los algoritmos.