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

DOI10.1007/s00224-009-9188-4zbMath1203.05104MaRDI 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 graphs; planar graph isomorphism; unambiguous logspace

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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

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