Planar Graphs: Logical Complexity and Parallel Isomorphism Tests

DOI10.1007/978-3-540-70918-3_58MaRDI QIDQ3590975zbMATHOpenAlexFDO

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

Mathematics Subject Classification ID

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)

Recommendations

• Testing Graph Isomorphism in Parallel by Playing a Game
• 3-connected Planar Graph Isomorphism is in Log-space
• Isomorphism of planar graphs (working paper)
• The Weisfeiler-Leman dimension of planar graphs is at most 3
• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3

Cited in

(13)

• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• The Weisfeiler-Leman dimension of planar graphs is at most 3
• Fixed-point definability and polynomial time on graphs with excluded minors
• Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
• scientific article; zbMATH DE number 4060741 (Why is no real title available?)
• Count-free Weisfeiler-Leman and group isomorphism
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Testing Graph Isomorphism in Parallel by Playing a Game
• Combinatorial refinement on circulant graphs
• scientific article; zbMATH DE number 6146491 (Why is no real title available?)

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)