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 greater than or equal to 3, a straight-line embedding on a grid of size (n - 2) x (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.