Find correspondences of nodes between two graphs

Question

I have two graphs (actually two street maps, one very fine grained and exact, the other coarser and maybe a bit faulty w.r.t. the nodes coordinates and the topology) and I want to find corresponding nodes and or edges between those two graphs. The nodes in the graph have a location in a global map (but the locations might differ a bit between corresponding nodes in the two graphs). Is there some standard approximation algorithm for that problem?

Answer 1

This is also known as the network alignment problem. Here is an example algorithm for dealing with this problem: GHOST

More details can be found in this bachelor's thesis:Survey on the Graph Alignment Problem and a Benchmark of Suitable Algorithms