Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-20877-5_52 | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
cycle space,bounded space complexity,corresponding construction problem,logspace algorithm,bounded genus case,3-connected planar graph,planarity testing,simple planar,unique embedding,planar embedding,deterministic logarithmic space | Discrete mathematics,Combinatorics,Embedding,Planarity testing,Change of basis,Planar straight-line graph,Book embedding,Cycle space,Mathematics,Planar graph,Bounded function | Conference |
Volume | ISSN | Citations |
abs/1101.2 | 0302-9743 | 3 |
PageRank | References | Authors |
0.50 | 18 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Samir Datta | 1 | 200 | 19.82 |
| Gautam Prakriya | 2 | 3 | 0.50 |