LIPIcs.FSTTCS.2008.1749.pdf
- Filesize: 385 kB
- 8 pages
Document
3-connected Planar Graph Isomorphism is in Log-space
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2008-12-05
Cite As Get BibTex
Samir Datta, Nutan Limaye, and Prajakta Nimbhorkar. 3-connected Planar Graph Isomorphism is in Log-space. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 155-162, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1749
Abstract
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.
Subject Classification
Keywords
- Planar graph isomorphism
- three connected graphs
- logspace
- universal exploration sequence
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads