The isomorphism problem for planar 3-connected graphs is in unambiguous logspace

DOI10.1007/s00224-009-9188-4zbMath1203.05104OpenAlexW2019136393MaRDI QIDQ1959391

Thomas Thierauf, Fabian Wagner

Publication date: 6 October 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2008/1327/

zbMATH Keywords

three connected graphsplanar graph isomorphismunambiguous logspace

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (4)

Depth-first search in directed planar graphs, revisited ⋮ On the power of unambiguity in log-space ⋮ A Logspace Algorithm for Partial 2-Tree Canonization ⋮ Frameworks for designing in-place graph algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Planarity testing in parallel
• Completeness results for graph isomorphism.
• Universal traversal sequences with backtracking.
• Directed Planar Reachability Is in Unambiguous Log-Space
• Algorithm and Experiments in Testing Planar Graphs for Isomorphism
• A Logspace Algorithm for Partial 2-Tree Canonization
• Hardness Results for Tournament Isomorphism and Automorphism
• Undirected ST-connectivity in log-space
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• Testing Graph Isomorphism in Parallel by Playing a Game
• A taxonomy of problems with fast parallel algorithms
• Nondeterministic Space is Closed under Complementation
• Parallel Tree Contraction Part 2: Further Applications
• Efficient Planarity Testing
• On the Hardness of Graph Isomorphism
• A Set of Topological Invariants for Graphs
• Making Nondeterminism Unambiguous
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science

This page was built for publication: The isomorphism problem for planar 3-connected graphs is in unambiguous logspace