Parallel Algorithms in Graph Theory: Planarity Testing

Abstract

We present efficient $(O(\log ^2 n))$ parallel algorithms for two classical graph problems: planarity testing and finding triconnected components. The algorithms use only a polynomial number of processors. Previous algorithms used $\Omega (n)$ operations, regardless of the number of available processors.