文章基本信息

标题：3-connected Planar Graph Isomorphism is in Log-space
本地全文：下载
作者：Samir Datta ; Nutan Limaye ; Prajakta Nimbhorkar 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2008
卷号：2
页码：155-162
DOI：10.4230/LIPIcs.FSTTCS.2008.1749
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Planar graph isomorphism; three connected graphs; logspace; universal exploration sequence