An Optimal Parallel Algorithm for Graph Planarity (Extended 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. >

Authors

• Vijaya Ramachandran
• John H. Reif

Keywords

• Parallel algorithms
• Ear
• Phase change random access memory
• Polynomials
• Testing
• Concurrent computing
• Contracts
• Very large scale integration
• NASA
• Semiconductor device modeling
• Use Of Techniques
• Undirected
• Directed Graph
• Linear Time
• Weak Connections
• Non-planar
• Sequential Algorithm
• Pair Of Vertices
• Parallel Algorithm
• Simple Cycle
• Depth-first
• Lowest Common Ancestor
• Spanning Tree
• Euler Equations
• Planar Graphs
• Adjacent Vertices
• Joint Point
• Local Graph
• Pair Of Edges