Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-009 | 21st January 2011 18:20

Planarity Testing Revisited


Authors: Samir Datta, Gautam Prakriya
Publication: 28th January 2011 11:11
Downloads: 4051


Planarity Testing is the problem of determining whether a given graph is planar while planar embedding is the corresponding construction problem.
The bounded space complexity of these problems has been determined to be Logspace by Allender and Mahajan with the aid of Reingold's result . Unfortunately, the algorithm is quite daunting and
generalizing it to say, the bounded genus case seems a tall order.

In this work, we present a simple planar embedding algorithm running in logspace.
We hope this algorithm will be more amenable to generalization. The algorithm is based on the fact that $3$-connected planar graphs have a unique embedding, a variant of Tutte's criterion on conflict graphs of cycles and an explicit
change of cycle basis.

We also present a logspace algorithm to find obstacles to planarity, viz. a Kuratowski minor, if the graph is non-planar. To the best of our knowledge this is the first logspace algorithm for this problem.

ISSN 1433-8092 | Imprint