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
DOI : 10.1137/1.9781611974782.36

I. Abraham, D. Delling, A. Fiat, A. Goldberg, and R. Werneck, Highway dimension and provably efficient shortest path algorithms, 2013.
DOI : 10.1145/2985473

I. Abraham, D. Delling, A. Fiat, A. V. Goldberg, and R. F. Werneck, VC-Dimension and Shortest Path Algorithms, ICALP, pp.690-699, 2011.
DOI : 10.1137/1116025

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

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, pp.782-793, 2010.
DOI : 10.1137/1.9781611973075.64
URL : http://research.microsoft.com/pubs/115272/soda10.pdf

T. Akiba, Y. Iwata, and Y. Yoshida, Dynamic and historical shortest-path distance queries on large evolving networks by pruned landmark labeling, Proceedings of the 23rd international conference on World wide web, WWW '14, pp.237-248, 2014.
DOI : 10.1145/2566486.2568007

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

S. Alstrup, S. Dahlgaard, M. B. , T. Knudsen, and E. Porat, Sublinear distance labeling, 24th Annual European Symposium on Algorithms Schloss Dagstuhl -Leibniz-Zentrum fuer Informatik, 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.
DOI : 10.1137/1.9781611974782.94
URL : http://epubs.siam.org/doi/pdf/10.1137/1.9781611974782.94

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 Proceedings , volume 1136 of Lecture Notes in Computer Science, pp.514-528, 1996.

H. Bast, S. Funke, D. Andrew, V. Goldberg, and D. S. Johnson, Ultrafast shortest-path queries via transit nodes, Camil Demetrescu Proceedings of a DIMACS Workshop, 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 Journal on Computing, vol.41, issue.6, pp.1380-1425, 2012.
DOI : 10.1137/110826655
URL : http://epubs.siam.org/doi/pdf/10.1137/1.9781611973068.101

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.51, issue.6, pp.361-381, 2012.
DOI : 10.1007/3-540-44676-1_3
URL : http://www.fmf.uni-lj.si/~cabello/publications/cabello-pairsofpaths-2009.pdf

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.
DOI : 10.1007/s004530010016

B. Chazelle, Computing on a free tree via complexity-preserving mappings, Algorithmica, vol.14, issue.1-4, pp.337-361, 1987.
DOI : 10.1145/322154.322161

S. Chechik, Approximate distance oracles with constant query time, Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC '14, pp.654-663, 2014.
DOI : 10.1145/2530531

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

E. Cohen, Using Selective Path-Doubling for Parallel Shortest-Path Computations, Journal of Algorithms, vol.22, issue.1, pp.30-56, 1997.
DOI : 10.1006/jagm.1996.0813

E. Cohen, Polylog-time and near-linear work approximation scheme for undirected shortest paths, Journal of the ACM, vol.47, issue.1, pp.132-166, 2000.
DOI : 10.1145/331605.331610

E. Cohen, E. Halperin, H. Kaplan, and U. Zwick, Reachability and Distance Queries via 2-Hop Labels, SIAM Journal on Computing, vol.32, issue.5, pp.1338-1355, 2003.
DOI : 10.1137/S0097539702403098
URL : http://www.cs.tau.ac.il/%7Ezwick/papers/2hop-SODA.ps.gz

V. Cohen-addad, S. Dahlgaard, and C. Wulff-nilsen, Fast and Compact Exact Distance Oracle for Planar Graphs, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp.962-973, 2017.
DOI : 10.1109/FOCS.2017.93
URL : http://arxiv.org/pdf/1702.03259

D. Delling, A. V. Goldberg, T. Pajor, and R. F. Werneck, Robust Distance Queries on Massive Networks, Algorithms -ESA 2014 -22th Annual European Symposium, pp.321-333, 2014.
DOI : 10.1007/978-3-662-44777-2_27

H. Djidjev, On-line algorithms for shortest path problems on planar digraphs, Graph-Theoretic Concepts in Computer Science, 22nd International Workshop, WG '96 Proceedings, volume 1197 of Lecture Notes in Computer Science, pp.151-165, 1996.
DOI : 10.1007/3-540-62559-3_14
URL : http://www.dcs.warwick.ac.uk/people/academic/Hristo.Djidjev/papers/planar-spp.ps.Z

M. Elkin and O. Neiman, Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp.9-11, 2016.
DOI : 10.1109/FOCS.2016.22
URL : http://arxiv.org/pdf/1605.04538

J. Fakcharoenphol and S. Rao, Planar graphs, negative weight edges, shortest paths, and near linear time, Journal of Computer and System Sciences, vol.72, issue.5, pp.868-889, 2006.
DOI : 10.1016/j.jcss.2005.05.007

A. Farzan and S. Kamali, Compact Navigation and Distance Oracles for Graphs with Small Treewidth, Algorithmica, vol.8, issue.1, pp.92-116, 2014.
DOI : 10.1007/3-540-44676-1_3
URL : http://www.cs.uwaterloo.ca/research/tr/2011/CS-2011-15.pdf

C. Gavoille and D. Peleg, Distance labeling in graphs, Journal of Algorithms, vol.53, issue.1, pp.85-112, 2004.
DOI : 10.1016/j.jalgor.2004.05.002
URL : https://hal.archives-ouvertes.fr/hal-00307381

P. Gawrychowski, A. Kosowski, and P. Uznanski, Sublinear-Space Distance Labeling Using Hubs, Distributed Computing -30th International Symposium, DISC 2016 Proceedings, volume 9888 of Lecture Notes in Computer Science, pp.230-242, 2016.
DOI : 10.1137/1.9781611973105.39
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, pp.515-529, 2018.
DOI : 10.1137/1.9781611975031.34
URL : http://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.34

R. Geisberger, P. Sanders, D. Schultes, and D. Delling, Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks, Experimental Algorithms, 7th International Workshop Proceedings, pp.319-333, 2008.
DOI : 10.1007/978-3-540-68552-4_24

A. V. Goldberg, H. Kaplan, and R. F. Werneck, *: Efficient Point-to-Point Shortest Path Algorithms, ALENEX, pp.129-143, 2006.
DOI : 10.1137/1.9781611972863.13
URL : http://www.math.tau.ac.il/~haimk/papers/msr-tr-2005-132.pdf

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, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1462-1478
DOI : 10.1137/1.9781611974782.95
URL : https://hal.archives-ouvertes.fr/hal-01359084

D. Peleg and A. A. Schäffer, Graph spanners, Journal of Graph Theory, vol.5, issue.1, pp.99-116, 1989.
DOI : 10.1007/978-1-4612-1098-6

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.
DOI : 10.1007/978-1-4684-2001-2_9

H. Shi and T. H. Spencer, Time???Work Tradeoffs of the Single-Source Shortest Paths Problem, Journal of Algorithms, vol.30, issue.1, pp.19-32, 1999.
DOI : 10.1006/jagm.1998.0968

M. Thorup, Shortcutting Planar Digraphs, Combinatorics, Probability and Computing, vol.1, issue.03, pp.287-315, 1995.
DOI : 10.1137/0136016

M. Thorup, Parallel Shortcutting of Rooted Trees, Journal of Algorithms, vol.23, issue.1, pp.139-159, 1997.
DOI : 10.1006/jagm.1996.0829

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