OPTIMAL PARALLEL ALGORITHMS FOR STRAIGHT-LINE GRID EMBEDDINGS OF PLANAR GRAPHS

作     者：KAO, MY FURER, M HE, X RAGHAVACHARI, B 

作者机构：PENN STATE UNIVDEPT COMP SCIUNIVERSITY PKPA 16802 SUNY BUFFALODEPT COMP SCIBUFFALONY 14260 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：1994年第7卷第4期

页      面：632-646页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：PLANAR GRAPHS STRAIGHT-LINE GRID EMBEDDINGS PARALLEL ALGORITHMS 

摘      要：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.