Planarity Testing Revisited

Details Planarity Testing Revisited Planarity Testing Revisited

2011-01-13

arxiv.org/abs/1101.2637v1

Computer Science

Computational Complexity

Scientific paper

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 exactly 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.% for planar graphs. 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.

Affiliated with

Also associated with

No associations

Rating

Planarity Testing Revisited does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Planarity Testing Revisited, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Planarity Testing Revisited will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-67150