Parallel Algorithms in Graph Theory: Planarity Testing
- 1 May 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 11 (2) , 314-328
- https://doi.org/10.1137/0211024
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.
Keywords
This publication has 16 references indexed in Scilit:
- Fast, Efficient Parallel Algorithms for Some Graph ProblemsSIAM Journal on Computing, 1981
- A Survey of Parallel Algorithms in Numerical Linear AlgebraSIAM Review, 1978
- An improved parallel processor bound in fast matrix inversionInformation Processing Letters, 1978
- Parallelism in random access machinesPublished by Association for Computing Machinery (ACM) ,1978
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithmsJournal of Computer and System Sciences, 1976
- Fast Parallel Matrix Inversion AlgorithmsSIAM Journal on Computing, 1976
- A characterization of the power of vector machinesJournal of Computer and System Sciences, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- The Parallel Evaluation of General Arithmetic ExpressionsJournal of the ACM, 1974
- On the maps of an n-sphere into another n-sphereDuke Mathematical Journal, 1937