2026-07-20T14:47:53Z https://drops.dagstuhl.de/oai

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

3-connected Planar Graph Isomorphism is in Log-space Datta, Samir Limaye, Nutan Nimbhorkar, Prajakta Planar graph isomorphism three connected graphs logspace universal exploration sequence We consider the isomorphism and canonization problem for $3$-connected planar graphs. The problem was known to be \Log-hard and in \ULcoUL\ \cite{TW07}. In this paper, we give a deterministic log-space algorithm for $3$-connected planar graph isomorphism and canonization. This gives an \Log-completeness result, thereby settling its complexity. \par The algorithm uses the notion of universal exploration sequences from \cite{koucky01} and \cite{Rei05}. To our knowledge, this is a completely new approach to graph canonization. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Nutan Limaye and Prajakta Nimbhorkar 2008 Is Part Of LIPIcs, Volume 2, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2008.1749 urn:nbn:de:0030-drops-17491 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2008.1749 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode