The graph isomorphism problem on geometric graphs

MaRDI QIDQ2928583zbMATH OpenFDO

Authors Ryuhei Uehara

Publication date 10 November 2014

Published in Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/2528/0.html

zbMATH Keywords

graph isomorphismintersection graphunit grid intersection graphgraph recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Logical Approaches to Computational Barriers
• Some recognition problems related to graph isomorphism
• Graph isomorphism for unit square graphs
• scientific article; zbMATH DE number 3841910
• Graph isomorphism is in the low hierarchy

Cited in

(8)

• Logical Approaches to Computational Barriers
• A vertex ordering characterization of simple-triangle graphs
• The motif problem: Geometric representations of sets of equivalence relations
• The isomorphism problem for rose window graphs
• Graph isomorphism and equality of simplices
• Graph isomorphism for unit square graphs
• A recognition algorithm for simple-triangle graphs
• scientific article; zbMATH DE number 7559375 (Why is no real title available?)

This page was built for publication: The graph isomorphism problem on geometric graphs

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