Optimal EREW parallel algorithms for connectivity, eardecomposition and st-numbering of planar graphs

摘要

Parallel EREW deterministic algorithms for finding the connectedcomponents, ear decomposition and st-numbering of a planar graph arepresented. The algorithms take O(log(n)) time with_log(n)/^n+m processors. Previous results have thesame complexity, but use the CRCW model. The same algorithms can be usedfor graphs with low genus. Let g be the genus of the minimalembedding of the graph, n the number of vertices and mthe number of edges. The new algorithm takes T=O(log(n)+log²(g)) time and using optimal spaceand P=O(_log(n)/^n+m) processors