O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs

Martin Fuerer; Xin He; Ming Yang Kao; Balaji Raghavachari

O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs

Martin Fuerer^*, Xin He, Ming Yang Kao, Balaji Raghavachari

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

4 Scopus citations

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

General Engineering

Cite this

@inproceedings{633277888eae4712acf66e98c762bf18,

title = "O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs",

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.",

author = "Martin Fuerer and Xin He and Kao, {Ming Yang} and Balaji Raghavachari",

year = "1992",

month = dec,

day = "1",

language = "English (US)",

isbn = "089791483X",

pages = "410--419",

booktitle = "4th Annual ACM Symposium on Parallel Algorithms and Architectures",

publisher = "Publ by ACM",

note = "4th Annual ACM Symposium on Parallel Algorithms and Architectures - SPAA '92 ; Conference date: 29-06-1992 Through 01-07-1992",

}

TY - GEN

T1 - O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs

AU - Fuerer, Martin

AU - He, Xin

AU - Kao, Ming Yang

AU - Raghavachari, Balaji

PY - 1992/12/1

Y1 - 1992/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026973481&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026973481&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0026973481

SN - 089791483X

SP - 410

EP - 419

BT - 4th Annual ACM Symposium on Parallel Algorithms and Architectures

PB - Publ by ACM

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

Y2 - 29 June 1992 through 1 July 1992

ER -

O(n log log n)-work parallel algorithms for straight-line grid embeddings of planar graphs

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this