1995/12/01 by Michael T. Goodrich · 110 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Algorithms and Data Compression #Graph Theory and Algorithms #Combinatorics #Separator (oil production) #Polygon (computer graphics) #Mathematics #Binary logarithm #Binary tree #Planar graph #Time complexity #Simple polygon #Graph #Computer science #Discrete mathematics #Monotone polygon #Physics #Geometry
paper · doi:10.1006/jcss.1995.1076
published in Journal of Computer and System Sciences 51(3), 374-389 (Elsevier BV)
openalex publication_date 1995/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/23
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.