Street maps might not be drawn to scale, but they are __________ equivalent.

71 Views Asked by At

"Topologically equivalent" could be used to describe the relationship between a mug and a doughnut; the same term could be used to describe the relationship between some graphs, such as these two:

Graph 1

Graph 2

However, the equivalence in street maps is different. If the two images above were street maps (possibly not drawn to scale) instead, they would still be considered non-equivalent. Intuitively, node 13 is on the left side in the former, but node 13 is on the right side in the latter, so they can't be equivalent in the street map sense.

The following street map, however, is equivalent to the first image when treated as a street map:

Graph 3

While node 9 is so far away from the rest of the nodes, it preserves some sort of equivalence.

It seems like I would consider two street maps to be equivalent if and only if for all nodes $v$ in the map, when enumerating $v$'s edges in a clockwise (or anticlockwise) manner, the circular lists formed in both maps are equivalent.

What is this equivalence called?

1

There are 1 best solutions below

2
On BEST ANSWER

I think you are looking for homeomorphism, which is what is usually meant by "topologically equivalent", but embedded in the plane. In multiple dimensions you are right that a donut and coffee cup are equivalent, but embedded in the plane you only allow local stretching and twisting. The requirement of continuity allows you to keep the idea of left and right sides of a road. That says the first two graphs you show are not equivalent because the central roads are reversed.

Harder to capture is the idea that the local stretching and twisting should not be too severe. I would generally expect that the direction between any two objects on the map should be accurate to, say, $45^\circ$ and distances within $25\%$ or maybe $50\%$. The limits for these are dependent on the quality claimed by the map.