We show how to construct an O(root n)-separator decomposition of a pla
nar 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(root n)
-separator of that subgraph. We also show how to construct an O(n(epsi
lon))-way decomposition tree in parallel in O(log n) time so that each
node corresponds to a subgraph of G and stores an O(n(12+epsilon))-se
parator of that subgraph. We demonstrate the utility of such a separat
or decomposition by showing how it can be used in the design of a para
llel algorithm for triangulating a simple polygon deterministically in
O(log n) time using O(n/log n) processors on a CRCW PRAM. (C) 1995 Ac
ademic Press, Inc.