Optimal Parallel Algorithm for Finding st-Ambitus of a Planar Biconnected Graph

A cycle C passing through two specific vertices s and t of a biconnected graph is said to be an st-ambitus if its bridges do not interlace in some special way. We present algorithms for st-ambitus for planar biconnected graphs, which are much simpler than the one known for general graphs [MT]. Our algorithm runs in O(n) time on a sequential machine and (log n) parallel time using O(n/log n) processors on an EREW PRAM.