# Find topologically closest graph under constraints?

I have a series of spatial polygons on a 2D plane (Fig a). These polygons can be represented as a graph where neighbouring polygons are linked and the location of the nodes is dictated by the centroid of the polygon (e.g. Fig b).

I want to map each node to a point on a grid (e.g. Fig c) whilst maintaining as much topological similarity as possible. I.e. to find the graph (which will have the same number of nodes) that is most topologically similar to the existing graph but under two constraints:

• Each node must sit on its own unique point on the grid
• Once assigned, all nodes must be contiguous on the grid

By topologically similar I mean having the same neighbours and ideally having as similar as possible spatial relationships (e.g. polygons remain on similar sides of another).

I am aware that certain graph similarity methods could be used (e.g. https://wadsashika.wordpress.com/2014/09/19/measuring-graph-similarity-using-neighbor-matching/ and graph kernels can be understood to measure the similarity of graphs.

Is there any way of calculating / generating the graph that is most similar (optimal) given certain constraints (i.e. moving the nodes to a grid). I see it as an optimisation problem but I’m not aware of any formal algorithms that identify optimally similar graphs (when using topology as a metric).

Should any solutions exist i will be looking to implement them in R and thanks in advance for any insight!

## migrated from stackoverflow.comAug 9 '17 at 15:06

This question came from our site for professional and enthusiast programmers.

• There is a country in the example (on the south west end) that didn't get a node. This is not supposed to happen, right? – Hellen Aug 9 '17 at 15:19
• Thanks for pointing this out - in this case i believe it's the river. As the river narrows it becomes indiscernible from a border. (Apologies for not providing a higher resolution image). – Hamley Aug 10 '17 at 9:37

2. For each point i, generate some candidate shortest distances to target grid.