## Abstract

We present an optimal parallel algorithm for computing a cycle separator of an n-vertex embedded planar undirected graph in O(log n) time on n/log n processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log^{2}n) time on n/log n processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but with n processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.

Original language | English (US) |
---|---|

Pages (from-to) | 398-408 |

Number of pages | 11 |

Journal | Algorithmica |

Volume | 14 |

Issue number | 5 |

DOIs | |

State | Published - Nov 1995 |

## Keywords

- Cycle separators
- Depth-first search
- Parallel algorithms
- Planar graphs

## ASJC Scopus subject areas

- General Computer Science
- Computer Science Applications
- Applied Mathematics