2026-07-23T18:08:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1327 2024-03-06T10:33:02Z ddc:004 open_access

The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace Thierauf, Thomas Wagner, Fabian 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$. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Thomas Thierauf and Fabian Wagner 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1327 urn:nbn:de:0030-drops-13273 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1327 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode