## 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 planar graph with n ≥ 3, a straight-line embedding on a grid of size (n - 2) × (n - 2) can be computed deterministically in O(log n log log n) time with O(n log log n) work on a parallel random access machine. If randomization is used, the complexity is improved to O(log n) expected time with the same work bound. The parallel random access machine used by these algorithms allows concurrent reads and concurrent writes of the shared memory; in case of a write conflict, an arbitrary processor succeeds.

Original language | English (US) |
---|---|

Title of host publication | 4th Annual ACM Symposium on Parallel Algorithms and Architectures |

Publisher | Publ by ACM |

Pages | 410-419 |

Number of pages | 10 |

ISBN (Print) | 089791483X |

State | Published - Dec 1 1992 |

Event | 4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92 - San Diego, CA, USA Duration: Jun 29 1992 → Jul 1 1992 |

### Other

Other | 4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92 |
---|---|

City | San Diego, CA, USA |

Period | 6/29/92 → 7/1/92 |

## ASJC Scopus subject areas

- Engineering(all)