A New Dynamic Graph Structure for Large-Scale Transportation Networks

We present a new dynamic graph structure specifically suited for large-scale transportation networks. Our graph structure provides simultaneously three unique features: compactness, agility and dynamicity. All previously known graph structures could not support efficiently (or could not support at all) at least one of the aforementioned features, especially in large-scale transportation networks. We demonstrate the practicality and superiority of our new graph structure by conducting an experimental study for shortest route planning in large-scale European and USA road networks with a few dozen millions of nodes and edges. Our approach is the first one that concerns the dynamic maintenance of a large-scale graph with ordered elements using a contiguous part of memory, and which allows an arbitrary online reordering of its elements without violating its contiguity.