Carleton University
Technical Report TR-01-07
July 2001
O-Optimal Planar Embedding using Graph Seperators
Norbert Zeh
Abstract
We present a new algorithm to test whether a given graph G is planar and to compute a planar embedding ˆG of G if such an embedding exists. Our algorithmutilizes a fundamentally new approach based on graph separators to obtain such an embedding. The I/O-complexity of our algorithm is O(sort(N)). A simple simulation technique reduces the I/O-complexity of our algorithm to O(perm(N)). We prove a matching lower bound of W(perm(N)) I/Os for computing a planar embedding of a given planar graph.