Journal:SIAM Journal of Discrete Mathematics, Volume 7, pages 632-646, 1994.
Abstract. 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 >= 3, a straight-line embedding on a grid of size (n-2) by (n-2) can be computed deterministically in O(log n loglog n) time with O(n/log n loglog 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.