3-connected Planar Graph Isomorphism is in Log-space

DOI10.4230/LIPIcs.FSTTCS.2008.1749zbMath1248.68213OpenAlexW1626825371MaRDI QIDQ3165955

Nutan Limaye, Samir Datta, Prajakta Nimbhorkar

Publication date: 19 October 2012

Full work available at URL: http://subs.emis.de/LIPIcs/frontdoor_14d0.html

zbMATH Keywords

logspace3-connected graphsplanar graph isomorphismuniversal exploration sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

On the complexity of matroid isomorphism problem ⋮ Graphs of Bounded Treewidth Can Be Canonized in  $\mbox{{\sf AC}$^1$}$ ⋮ Planarity Testing Revisited ⋮ Graph isomorphism restricted by lists ⋮ On the Complexity of Matroid Isomorphism Problems

This page was built for publication: 3-connected Planar Graph Isomorphism is in Log-space