Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs

A straight-line grid embedding of a planar graph is a drawing of the graph on a plane where the vertices are located at grid points and the edges are represented by nonintersecting segments of straight, lines joining their incident vertices. Given an n-vertex embedded planar graph with $n \geq 3$, a straight-line embedding on a grid of size $( n - 2 ) \times ( n - 2 )$ can be computed deterministically in $O( \log n\log \log n )$ time with $n/\log n\log \log n$ processors. If randomization is used, the complexity is improved to $O( \log n )$ expected time with the same optimal linear work. These algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes of the shared memory and permits an arbitrary processor to succeed in case of a write conflict.