A Parallel Algorithm for Finding a Separator in Planar Graphs

We present a randomized parallel algorithm for finding a simple cycle separator in a planar graph. The size of the separator is O(√n) and it separates the graph so that the largest part contains at most 2/8 · n vertices. Our algorithm takes T = O(log2(n)) time and P = O(n + f1+ε) processors, where n is the number of vertices, f is the number of faces and ε is any positive constant. The algorithm is based on the solution of Lipton and Tarjan [8] for the sequential case which takes O(n) time. Combining our algorithm with the Pan and Reif [12] algorithm, enables us to find a BFS of planar graph in time O(log3(n)) using n1. 5/log(n) processors. Using a variation of our algorithm we can construct a simple cycle separator of size O(d · √f) were d is maximum face size.

Authors

• Hillel Gazit
• Gary L. Miller

Keywords

• Parallel algorithms
• Particle separators
• Transmission line matrix methods
• Very large scale integration
• Numerical analysis
• Tree graphs
• Computer science
• Algorithm design and analysis
• Routing
• Parallel Algorithm
• Planar Graphs
• Matrix Multiplication
• Simple Cycle
• Face Size
• Independent Set
• Layering
• Voronoi Diagram
• Divide-and-conquer
• Maximal Set
• Breadth-first Search
• Maximum Independent Set
• Set Of Faces
• Number Of Processors
• Graph Problems