Parallel Algorithms in Graph Theory: Planarity Testing
Joseph F. JáJá, Janoš Šimon · SIAM Journal on Computing · 1982
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.