OSRM's edge-expansion [document]

[kkdd]

Hello,
Is OSRM's edge-expansion related to the edge-expansion in graph theory?

[TheMarex]

@kkdd No it refers to creating a turn-based graph where edges are turns and nodes are street segments. We need this to model turn restrictions.

[daniel-j-h]

@danpat did a beautiful job of visualizing these concepts in:

https://github.com/Project-OSRM/osrm-backend/wiki/Graph-representation

Closing here as not actionable.

[kkdd]

Thank you.
What is this transformation called in the literature of graph theory?

[chaupow]

Hi @kkdd, I think if you ask about pure graph theory, it's difficult to say because it only applies to graphs with turn restrictions. I guess the original graph is a graph with turn restriction and the edge-expanded graph is a dual graph representation.

However, I did a quick google search, and in route planning there seem to be different expressions used:

• Edge-based graph
• Line graphs
• Linear dual graph
• Dual transformation

tl;dr

There is no clearly defined name for this transformation

[kkdd]

Hello,
I eventually succeeded to find its name: "Line graph" in Wikipedia!