An efficient parallel algorithm for planarity (Q1114415)

The authors give a parallel algorithm for testing graph planarity, and for finding an embedding of a planar graph. Their algorithm runs in \(O(\log^ 2 n)\) steps on n processors of a CREW PRAM. This is an improvement to a previous best parallel algorithm due to Ja'Ja' and Simon. The new algorithm uses efficient parallel algorithms for manipulating a sophisticated data structure for representing sets of embeddings - the PQ-tree originally invented by Booth and Lueker.