Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
DOI10.1007/978-3-540-70918-3_58zbMATH Open1186.68215OpenAlexW1656942156MaRDI QIDQ3590975FDOQ3590975
Authors: Oleg Verbitsky 
Publication date: 3 September 2007
Published in: STACS 2007 (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-70918-3_58
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Planar graphs; geometric and topological aspects of graph theory (05C10) Descriptive complexity and finite models (68Q19)
Cited In (13)
- Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
- Fixed-point definability and polynomial time on graphs with excluded minors
- Fixed-point definability and polynomial time on chordal graphs and line graphs
- The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
- Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
- Combinatorial refinement on circulant graphs
- The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
- Title not available (Why is that?)
- The Weisfeiler-Leman dimension of planar graphs is at most 3
- Distributed Testing of Graph Isomorphism in the CONGEST Model.
- Title not available (Why is that?)
- Testing Graph Isomorphism in Parallel by Playing a Game
- Count-free Weisfeiler-Leman and group isomorphism
This page was built for publication: Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590975)
