Road/Transportation network project at Gang

Gang team designs network and graph algorithms. This page is dedicated to experiments on road and transportation networks.
People involved: Emmanuel Arrighi, Cyprien Bouni, Michel Habib, Adrian Kosowski, Olivier Marty, Duc-Minh Phan, Nishant Rai, Parth Shah, Laurent Viennot (contact).

Demos (zoom in OpenStreetMap)

Dimater, radius, and longest road trips

Skeleton trees: visualize all your trips

Data

• Road networks computed from GeoFrabrik data that was extracted from OpenStreetMap data.

Papers

• [7] Exploiting Hopsets: Improved Distance Oracles for Graphs of Constant Highway Dimension and Beyond. Local version. Siddharth Gupta and Adrian Kosowski and Laurent Viennot. ICALP'2019.
• [6] Hardness of exact distance queries in sparse graphs through hub labeling. Local version. Adrian Kosowski and Przemyslaw Uznanski and Laurent Viennot. PODC'2019.
• [5] Fast Public Transit Routing with Unrestricted Walking through Hub Labeling. Local version. Duc-Minh Phan and Laurent Viennot. SEA2'2019.
• [4] Beyond Highway Dimension: Small Distance Labels Using Tree Skeletons. Local version. Slides. Adrian Kosowski and Laurent Viennot. Proceedings of the Nineteenth Annual {ACM-SIAM} Symposium on Discrete Algorithms, {SODA} 2017, Barcelone, Spain, January 20-22, 2017, 2017.
• [3] Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs: With an application to the six degrees of separation games. Local version. Michele Borassi and Pierluigi Crescenzi and Michel Habib and Walter A. Kosters and Andrea Marino and Frank W. Takes. Theor. Comput. Sci., 2015.
• [2] On the Solvability of the Six Degrees of Kevin Bacon Game - A Faster Graph Diameter and Radius Computation Method. Local version. Michele Borassi and Pierluigi Crescenzi and Michel Habib and Walter A. Kosters and Andrea Marino and Frank W. Takes. 2014.
• [1] On computing the diameter of real-world undirected graphs. Local version. Pilu Crescenzi and Roberto Grossi and Michel Habib and Leonardo Lanzi and Andrea Marino. Theor. Comput. Sci., 2013.

Acknowledgements

• Street and map information is provided by OpenStreetMap contributors.
• We used data extracted by GeoFrabrik in September 2015 from OpenStreetMap data.
• Visualization relies on OpenStreetMap, Leaflet and MapBox.
• The cluster that performed the computations is maintained by the SED team of Inria Paris.