We present a new dynamic graph structure specifically suited for large-scale transportation networks that provides simultaneously three unique features: compactness, agility and dynamicity. We demonstrate its practicality and superiority by conducting an experimental study for shortest route planning in large-scale European and US 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 memory part, and which allows an arbitrary online reordering of its elements.