Isomorphism testing for embeddable graphs through definability

DOI10.1145/335305.335313MaRDI QIDQ3191972zbMATH OpenOpenAlexFDO

Authors Martin Grohe

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335313

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) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• The Weisfeiler--Leman Dimension of Planar Graphs Is at Most 3
• Fixed-point definability and polynomial time on graphs with excluded minors
• Testing Graph Isomorphism in Parallel by Playing a Game
• The Weisfeiler-Leman dimension of planar graphs is at most 3
• The power of the Weisfeiler-Leman algorithm to decompose graphs

Cited in

(22)

• Permutation group approach to association schemes
• Succinct definitions in the first order theory of graphs
• The first order definability of graphs with separators via the Ehrenfeucht game
• From Invariants to Canonization in Parallel
• Testing Graph Isomorphism in Parallel by Playing a Game
• Counting and sampling minimum cuts in genus g graphs
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• The Weisfeiler-Leman dimension of planar graphs is at most 3
• On the Weisfeiler-Leman dimension of finite groups
• CFI Construction and Balanced Graphs
• Fixed-point definability and polynomial time on graphs with excluded minors
• Global minimum cuts in surface embedded graphs
• Canonisation and Definability for Graphs of Bounded Rank Width
• Minimum Cuts in Surface Graphs
• Spectra of symmetric powers of graphs and the Weisfeiler-Lehman refinements
• Canonization for bounded and dihedral color classes in choiceless polynomial time
• Graph isomorphism in quasipolynomial time parameterized by treewidth
• Graph isomorphism and multivariate graph spectrum
• Canonizing graphs of bounded rank-width in parallel via Weisfeiler-Leman
• Logarithmic Weisfeiler-Leman identifies all planar graphs
• The first order definability of graphs: Upper bounds for quantifier depth
• Hashing and canonicalizing Notation 3 graphs

This page was built for publication: Isomorphism testing for embeddable graphs through definability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3191972)