Name of graph that represents street maps

137 Views Asked by At

When reading about practical uses of graph search, one type of example that I have seen in many places is for travelling through a network of roads from one physical location to another; in particular, in all of the examples that I've seen, each street intersection is represented as a graph node, and each stretch of street between two intersections is represented as a graph edge.

However, because street intersections themselves have a transit cost (especially with stop signs and traffic lights), it seems to me that the opposite representation should be used:

Each node in the graph represents the midpoint of a stretch of street between two intersections.

Each edge in the graph represents movement from the midpoint of one street, through one street intersection, to midpoint of another street. The weight of this edge represents the combined travel time of the streets and the intersection.

If a street is two-way, there are two nodes representing its midpoint, one for each direction of travel; if the street is one-way, there is only one node for it's midpoint.

If a stretch of two-way street is free of "no u-turn signs", then the street's two nodes are have connections between each other, with weights representing how the amount of time needed to make a u-turn from one direction of travel to the other.

Each "no u-turn" sign is represented as the omission of a connection between a street's two nodes.

Similarly, for each sign at a street intersection which reads "no left turn" or "no right turn" or "do not enter", the corresponding edge is omitted from the graph.

What I would like to know, is if there is a name for this inverted representation? It's definitely not a "Dual graph", but I don't know what it is.