10.4230/LIPICS.STACS.2008.1327
Thierauf, Thomas
Thomas
Thierauf
Wagner, Fabian
Fabian
Wagner
The Isomorphism Problem for Planar 3-Connected Graphs is in Unambiguous Logspace
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
2008
Article
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
2008
2008-02-06
2008-02-06
2008-02-06
en
urn:nbn:de:0030-drops-13273
10.4230/LIPIcs.STACS.2008
978-3-939897-06-4
1868-8969
10.4230/LIPIcs.STACS.2008
LIPIcs, Volume 1, STACS 2008
25th International Symposium on Theoretical Aspects of Computer Science
2013
1
55
633
644
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Albers, Susanne
Susanne
Albers
Weil, Pascal
Pascal
Weil
1868-8969
Leibniz International Proceedings in Informatics (LIPIcs)
2008
1
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
12 pages
172539 bytes
application/pdf
Creative Commons Attribution-NoDerivs 3.0 Unported license
info:eu-repo/semantics/openAccess
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$.
LIPIcs, Vol. 1, 25th International Symposium on Theoretical Aspects of Computer Science, pages 633-644