Paper Info
Title
Optimal 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 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.
Year
DOI
Venue
1994
10.1137/S0895480191221453
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
PLANAR GRAPHS, STRAIGHT-LINE GRID EMBEDDINGS, PARALLEL ALGORITHMS
Journal
7
Issue
ISSN
Citations 
4
0895-4801
2
PageRank 
References 
Authors
0.70
0
4
Name
Order
Citations
PageRank
Ming-Yang Kao11520159.74
Xin He226135.69
Balaji Raghavachari3100177.77
Balaji Raghavachari4100177.77