3-connected Planar Graph Isomorphism is in Log-space

Authors Samir Datta, Nutan Limaye, Prajakta Nimbhorkar



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2008.1749.pdf
  • Filesize: 385 kB
  • 8 pages

Document Identifiers

Author Details

Samir Datta
Nutan Limaye
Prajakta Nimbhorkar

Cite AsGet 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.
Keywords
  • Planar graph isomorphism
  • three connected graphs
  • logspace
  • universal exploration sequence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail