Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs
Optimal Parallel Algorithms for Straight-Line Grid Embeddings of Planar Graphs
复制标题
平面图直线网格嵌入的最优并行算法
DOI：
10.1137/s0895480191221453
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
B. Raghavachari
中科院分区：
文献类型：
--
作者：
M. Kao;Martin Fürer;Xin He;B. Raghavachari
平面图的直线网格嵌入是图形在平面上的图形图，该图形位于网格点处，边缘通过非直接段的直线段表示，线条连接了其入射顶点。给定n -vertex嵌入式平面图，带有$ n \ geq 3 $，可以按$ o（\ log o（\ log）确定地计算出大小$ $ $（n -2）\ times（n -2）\ times（n -2）$（n -2）$（n -2）$的直线嵌入n \ log \ log n）$ time带有$ n/\ log n \ log \ log n $处理器。如果使用随机化，则使用相同的最佳线性工作将复杂性提高到$ O（\ log n）$预期时间。这些算法在平行的随机访问机上运行，该计算机允许同时读取共享内存，并允许任意处理器在写入冲突的情况下成功。
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.