Planar Separators and Parallel Polygon Triangulation

作者:

Highlights:

摘要

We show how to construct an O(√n)-separator decomposition of a planar graph G in O(n) time. Such a decomposition defines a binary tree, where each node corresponds to a subgraph of G and stores an O(√n)-separator of that subgraph. We also show how to construct an O(nϵ)-way decomposition tree in parallel in O(log n) time so that each node corresponds to a subgraph of G and stores an O(n12+ϵ)-separator of that subgraph. We demonstrate the utility of such a separator decomposition by showing how it can be used in the design of a parallel algorithm for triangulating a simple polygon deterministically in O(log n) time using O(n/log n) processors on a CRCW PRAM.

论文关键词:

论文评审过程:Available online 25 May 2002.

论文官网地址:https://doi.org/10.1006/jcss.1995.1076