Planar Graphs: Logical Complexity and Parallel Isomorphism Tests

DOI10.1007/978-3-540-70918-3_58MaRDI QIDQ3590975zbMATH OpenOpenAlexFDO

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

Planar graphs; geometric and topological aspects of graph theory (05C10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25)

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

(17)

• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Testing Graph Isomorphism in Parallel by Playing a Game
• Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems
• scientific article; zbMATH DE number 4060741 (Why is no real title available?)
• scientific article; zbMATH DE number 6146491 (Why is no real title available?)
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
• 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
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• Count-free Weisfeiler-Leman and group isomorphism
• Combinatorial refinement on circulant graphs
• The iteration number of colour refinement
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• The iteration number of the Weisfeiler-Leman algorithm
• Logarithmic Weisfeiler-Leman identifies all planar graphs

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)