Optimal EREW parallel algorithms for connectivity, ear decomposition and st-numbering of planar graphs
Hillel Gazit · 2002
Parallel EREW deterministic algorithms for finding the connected components, ear decomposition and st-numbering of a planar graph are presented. The algorithms take O(log(n)) time with /sub log(n)///sup n+m/ processors. Previous results have the same complexity, but use the CRCW model. The same algorithms can be used for graphs with low genus. Let g be the genus of the minimal embedding of the graph, n the number of vertices and m the number of edges. The new algorithm takes T=O(log(n)+log/sup 2/(g)) time and using optimal space and P=O(/sub log(n)///sup n+m/) processors.>