Tipus de document
Treball de fi de grauData de publicació
Llicència de publicació
Si us plau utilitzeu sempre aquest identificador per citar o enllaçar aquest document: https://hdl.handle.net/2445/227948
Aplicaciones del criterio de planaridad de Mac Lane en algoritmos paralelos
Títol de la revista
Autors
Director/Tutor
ISSN de la revista
Títol del volum
Recurs relacionat
Resum
[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.
Descripció
Treballs Finals de Grau d'Enginyeria Informàtica, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2025, Director: Kolja Knauer i Santi Segui Mesquida
Matèries (anglès)
Citació
Citació
RASO ALONSO, Carlos. Aplicaciones del criterio de planaridad de Mac Lane en algoritmos paralelos. [consulted: 22 of May of 2026]. Available at: https://hdl.handle.net/2445/227948