A. Abboud, G. Bodwin, and S. Pettie, A hierarchy of lower bounds for sublinear additive spanners, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.568-576, 2017.

I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck, VCdimension and shortest path algorithms, ICALP, vol.6755, pp.690-699, 2011.

I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway dimension and provably efficient shortest path algorithms, J. ACM, vol.63, issue.5, 2016.
DOI : 10.1145/2985473

I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway dimension and provably efficient shortest path algorithms, J. ACM, vol.63, issue.5, 2016.

I. Abraham, A. Fiat, A. V. Goldberg, and R. F. Werneck, Highway dimension, shortest paths, and provably efficient algorithms, Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, pp.782-793, 2010.
DOI : 10.1137/1.9781611973075.64
URL : https://epubs.siam.org/doi/pdf/10.1137/1.9781611973075.64

T. Akiba, Y. Iwata, and Y. Yoshida, Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling

, 23rd International World Wide Web Conference, WWW '14, pp.237-248, 2014.

N. Alon and B. Schieber, Optimal preprocessing for answering on-line product queries, 1987.

S. Alstrup, S. Dahlgaard, M. Baek-tejs-knudsen, and E. Porat, Sublinear distance labeling, 24th Annual European Symposium on Algorithms, ESA 2016, vol.57, pp.1-5, 2016.

H. Angelidakis, Y. Makarychev, and V. Oparin, Algorithmic and hardness results for the hub labeling problem, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1442-1461, 2017.

D. Z. Srinivasa-rao-arikati, L. P. Chen, G. Chew, . Das, H. M. Michiel et al., Planar spanners and approximate shortest path queries among obstacles in the plane, Algorithms -ESA '96, Fourth Annual European Symposium, vol.1136, pp.514-528, 1996.

H. Bast, S. Funke, and D. Matijevic, Ultrafast shortest-path queries via transit nodes, The Shortest Path Problem, Proceedings of a DIMACS Workshop, vol.74, pp.175-192, 2006.
DOI : 10.1090/dimacs/074/07

A. Bhattacharyya, E. Grigorescu, K. Jung, S. Raskhodnikova, and D. P. Woodruff, Transitive-closure spanners, SIAM J. Comput, vol.41, issue.6, pp.1380-1425, 2012.
DOI : 10.1137/110826655
URL : http://arxiv.org/pdf/0808.1787

L. Hans, G. Bodlaender, N. Tel, and . Santoro, Trade-offs in non-reversing diameter, Nord. J. Comput, vol.1, issue.1, pp.111-134, 1994.

S. Cabello, Many distances in planar graphs, Algorithmica, vol.62, issue.1-2, pp.361-381, 2012.

S. Chaudhuri and C. D. Zaroliagis, Shortest paths in digraphs of small treewidth. part I: sequential algorithms, Algorithmica, vol.27, issue.3, pp.212-226, 2000.

B. Chazelle, Computing on a free tree via complexity-preserving mappings, Algorithmica, vol.2, pp.337-361, 1987.

D. Z. Chen and J. Xu, Shortest path queries in planar graphs, Proceedings of the ThirtySecond Annual ACM Symposium on Theory of Computing, pp.469-478, 2000.

E. Cohen, Using selective path-doubling for parallel shortest-path computations, J. Algorithms, vol.22, issue.1, pp.30-56, 1997.

E. Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, J. ACM, vol.47, issue.1, pp.132-166, 2000.

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, Reachability and distance queries via 2-hop labels, SIAM J. Comput, vol.32, issue.5, pp.1338-1355, 2003.

V. Cohen-addad, S. Dahlgaard, and C. Wulff-nilsen, Fast and compact exact distance oracle for planar graphs, 58th IEEE Annual Symposium on Foundations of Computer Science, pp.962-973, 2017.
URL : https://hal.archives-ouvertes.fr/hal-02169530

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck, Robust distance queries on massive networks, Algorithms -ESA 2014 -22th Annual European Symposium, vol.8737, pp.321-333, 2014.

H. Djidjev, On-line algorithms for shortest path problems on planar digraphs, Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96, vol.1197, pp.151-165, 1996.

M. Elkin and O. Neiman, Hopsets with constant hopbound, and applications to approximate shortest paths, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, pp.128-137, 2016.

M. Elkin and O. Neiman, Linear-size hopsets with small hopbound, and distributed routing with low memory, 2017.

J. Fakcharoenphol and S. Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, J. Comput. Syst. Sci, vol.72, issue.5, pp.868-889, 2006.

A. Farzan and S. Kamali, Compact navigation and distance oracles for graphs with small treewidth, Algorithmica, vol.69, issue.1, pp.92-116, 2014.

C. Gavoille and D. Peleg, Stéphane Pérennes, and Ran Raz, J. Algorithms, vol.53, issue.1, pp.85-112, 2004.

P. Gawrychowski, A. Kosowski, and P. Uznanski, Sublinear-space distance labeling using hubs, Distributed Computing -30th International Symposium, DISC 2016, pp.230-242, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01415064

P. Gawrychowski, S. Mozes, O. Weimann, and C. Wulff-nilsen, Better tradeoffs for exact distance oracles in planar graphs, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp.515-529, 2018.

R. Geisberger, P. Sanders, D. Schultes, and D. Delling, Contraction hierarchies: Faster and simpler hierarchical routing in road networks, Experimental Algorithms, 7th International Workshop, vol.5038, pp.319-333, 2008.

A. V. Goldberg, H. Kaplan, and R. F. Werneck, Reach for A*: Efficient point-to-point shortest path algorithms, ALENEX, pp.129-143, 2006.

R. J. Gutman, Reach-based routing: A new approach to shortest path algorithms optimized for road networks, ALENEX/ANALCO, pp.100-111, 2004.

N. Philip, S. Klein, and . Subramanian, A randomized parallel algorithm for single-source shortest paths, J. Algorithms, vol.25, issue.2, pp.205-220, 1997.

A. Kosowski and L. Viennot, Beyond highway dimension: Small distance labels using tree skeletons, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01359084

A. Kosowski and L. Viennot, Beyond highway dimension: Small distance labels using tree skeletons, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1462-1478, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01359084

D. Peleg and A. A. Schäffer, Graph spanners, Journal of Graph Theory, vol.13, issue.1, pp.99-116, 1989.

P. Raghavan and C. D. Thompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, vol.7, issue.4, pp.365-374, 1987.

H. Shi and T. H. Spencer, Time-work tradeoffs of the single-source shortest paths problem, J. Algorithms, vol.30, issue.1, pp.19-32, 1999.

M. Thorup, Shortcutting planar digraphs, Combinatorics, Probability & Computing, vol.4, pp.287-315, 1995.

M. Thorup, Parallel shortcutting of rooted trees, J. Algorithms, vol.23, issue.1, pp.139-159, 1997.

J. D. Ullman and M. Yannakakis, High-probability parallel transitive closure algorithms, SPAA, pp.200-209, 1990.