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

Ming-Yang Kao, Martin Fürer, Xin He, Balaji Raghavachari

Research output: Contribution to journalArticlepeer-review


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.
Original languageEnglish
Pages (from-to)632-646
JournalSIAM Journal on Discrete Mathematics
StatePublished - 1994

Fingerprint Dive into the research topics of 'Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs'. Together they form a unique fingerprint.

Cite this