An optimal parallel algorithm for graph planarity
- 1 January 1989
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 282-287
- https://doi.org/10.1109/sfcs.1989.63491
Abstract
The authors present a parallel algorithm based on open ear decomposition which, given a graph G on n vertices, constructs an embedding of G onto the plane or reports that G is nonplanar. This parallel algorithm runs on a concurrent-read, concurrent-write parallel random-access machine (CRCW PRAM) in O(log n) time with the same processor bound as graph connectivity.Keywords
This publication has 19 references indexed in Scilit:
- An efficient parallel algorithm for planarityJournal of Computer and System Sciences, 1988
- Parallel ear decomposition search (EDS) and st-numbering in graphsTheoretical Computer Science, 1986
- Computing ears and branchings in parallelPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Parallel tree contraction and its applicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Parallel Algorithms in Graph Theory: Planarity TestingSIAM Journal on Computing, 1982
- Computing an st-numberingTheoretical Computer Science, 1976
- Efficient Planarity TestingJournal of the ACM, 1974
- How to Draw a GraphProceedings of the London Mathematical Society, 1963
- Non-separable and planar graphsTransactions of the American Mathematical Society, 1932
- Sur le problème des courbes gauches en TopologieFundamenta Mathematicae, 1930