3-connected Planar Graph Isomorphism is in Log-space
From MaRDI portal
Planar graphs; geometric and topological aspects of graph theory (05C10) Connectivity (05C40) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)
Recommendations
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- scientific article; zbMATH DE number 6146491
- Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
- Dynamic complexity of planar 3-connected graph isomorphism
- P3-isomorphisms for graphs
- 3-connected planar graphs are 2-distinguishable with few exceptions
- Isomorphisms ofP3-graphs
- Characterizing 3-connected planar graphs and graphic matroids
- (3,3)-linked planar graphs
- Isomorphism of planar graphs (working paper)
Cited in
(9)- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Graph isomorphism for \(K_{3,3}\)-free and \(K_5\)-free graphs is in Log-space
- Graphs of bounded treewidth can be canonized in AC^1
- Planarity testing revisited
- On the Complexity of Matroid Isomorphism Problems
- Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
- scientific article; zbMATH DE number 6146491 (Why is no real title available?)
- Graph isomorphism restricted by lists
- On the complexity of matroid isomorphism problem
This page was built for publication: 3-connected Planar Graph Isomorphism is in Log-space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3165955)
