The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class $AC^1$. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to $UL cap coUL$. As a consequence of our method we get that the isomorphism problem for oriented graphs is in $NL$. We also show that the problems are hard for $L$.
@InProceedings{thierauf_et_al:LIPIcs.STACS.2008.1327, author = {Thierauf, Thomas and Wagner, Fabian}, title = {{The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {633--644}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1327}, URN = {urn:nbn:de:0030-drops-13273}, doi = {10.4230/LIPIcs.STACS.2008.1327}, annote = {Keywords: } }
Feedback for Dagstuhl Publishing