, Any other operation corresponds to an edge of the spanning path that is stabbed by a hyperedge of H ,G (? r ), and as a result there can only beÕ

A. Abboud, V. Williams, and J. Wang, Approximation and fixed parameter subquadratic algorithms for radius and diameter in sparse graphs, SODA, pp.377-391, 2016.

N. Alon, P. Seymour, and R. Thomas, A separator theorem for nonplanar graphs, Journal of the American Mathematical Society, vol.3, issue.4, pp.801-808, 1990.

M. Anthony, G. Brightwell, and C. Cooper, The Vapnik-Chervonenkis dimension of a random graph, Discrete Mathematics, vol.138, issue.1-3, pp.43-56, 1995.

A. Backurs, L. Roditty, G. Segal, V. Williams, and N. Wein, Towards tight approximation bounds for graph diameter and eccentricities, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp.267-280, 2018.

C. Berge, Graphs and hypergraphs, 1973.

V. Bilo, V. Goyal, R. Ravi, and M. Singh, On the crossing spanning tree problem, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp.51-60, 2004.

J. A. Bondy and U. S. Murty, Graph theory, 2008.

M. Borassi, P. Crescenzi, and M. Habib, Into the square: On the complexity of some quadratictime solvable problems, Electronic Notes in Theoretical Computer Science, vol.322, pp.51-67, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01390131

N. Bousquet, A. Lagoutte, Z. Li, A. Parreau, and S. Thomassé, Identifying codes in hereditary classes of graphs and VC-dimension, SIAM Journal on Discrete Mathematics, vol.29, issue.4, pp.2047-2064, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01038012

N. Bousquet and S. Thomassé, VC-dimension and Erd?s-Pósa property, Discrete Mathematics, vol.338, issue.12, pp.2302-2317, 2015.

A. Brandstädt, V. Chepoi, and F. Dragan, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Applied Mathematics, vol.82, issue.1-3, pp.43-77, 1998.

A. Brandstädt, F. Dragan, V. Chepoi, and V. Voloshin, Dually chordal graphs, SIAM Journal on Discrete Mathematics, vol.11, issue.3, pp.437-455, 1998.

K. Bringmann, T. Husfeldt, and M. Magnusson, Multivariate analysis of orthogonal range searching and graph distances parameterized by treewidth, In IPEC, 2018.

H. Brönnimann, B. Chazelle, and J. Matouvsek, Product range spaces, sensitive sampling, and derandomization, SIAM J. Comput, vol.28, issue.5, pp.1552-1575, 1999.

S. Cabello, Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs, ACM Transactions on Algorithms (TALG), vol.15, issue.2, p.21, 2018.

M. Cairo, R. Grossi, and R. Rizzi, New bounds for approximating extremal distances in undirected graphs, Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms (SODA 2016), pp.363-376, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01526665

T. Chan, Optimal partition trees, Discrete & Computational Geometry, vol.47, issue.4, pp.661-690, 2012.

B. Chazelle and E. Welzl, Quasi-optimal range searching in spaces of finite VC-dimension. Discrete & Computational Geometry, vol.4, pp.467-489, 1989.

S. Chechik, D. Larkin, L. Roditty, G. Schoenebeck, R. Tarjan et al., Better approximation algorithms for the graph diameter, Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pp.1041-1052, 2014.

V. Chepoi, B. Estellon, and Y. Vaxès, Covering planar graphs with a fixed number of balls, Discrete & Computational Geometry, vol.37, issue.2, pp.237-244, 2007.

M. Cohen, Y. Lee, and Z. Song, Solving linear programs in the current matrix multiplication time, STOC, pp.938-942, 2019.

D. Corneil, F. Dragan, M. Habib, and C. Paul, Diameter determination on restricted graph families, Discrete Applied Mathematics, vol.113, issue.2-3, pp.143-166, 2001.
URL : https://hal.archives-ouvertes.fr/lirmm-00090363

D. Coudert, G. Ducoffe, and A. Popa, Fully polynomial FPT algorithms for some classes of bounded clique-width graphs, SODA'18, pp.2765-2784, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01676187

S. Dahlgaard, On the hardness of partially dynamic graph problems and connections to diameter, 43rd International Colloquium on Automata, Languages, and Programming, vol.48, pp.1-48, 2016.

P. Damaschke, Computing giant graph diameters, IWOCA, pp.373-384, 2016.

R. Downey, P. Evans, and M. Fellows, Parameterized learning complexity, COLT, pp.51-57, 1993.

G. Ducoffe, A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters, 2nd Symposium on Simplicity in Algorithms, 2019.
URL : https://hal.archives-ouvertes.fr/hal-01974190

G. Ducoffe, M. Habib, and L. Viennot, Fast diameter computation within split graphs
URL : https://hal.archives-ouvertes.fr/hal-02307397

Z. Dvo?ák, On classes of graphs with strongly sublinear separators, European Journal of Combinatorics, vol.71, pp.1-11, 2018.

Z. Dvorak and S. Norin, Strongly sublinear separators and polynomial expansion, SIAM Journal on Discrete Mathematics, vol.30, issue.2, pp.1095-1101, 2016.

Z. Dvo?ák and S. Norin, Treewidth of graphs with balanced separations, Journal of Combinatorial Theory, Series B, vol.137, pp.137-144, 2019.

D. Eisenstat and D. Angluin, The VC dimension of k-fold union, Information Processing Letters, vol.101, issue.5, pp.181-184, 2007.

D. Eppstein, Diameter and treewidth in minor-closed graph families, Algorithmica, vol.27, issue.3-4, pp.275-291, 2000.

D. Eppstein, Dynamic generators of topologically embedded graphs, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.599-608, 2003.

J. Evald and S. Dahlgaard, Tight Hardness Results for Distance and Centrality Problems in Constant Degree Graphs, 2016.

A. Farley and A. Proskurowski, Computation of the center and diameter of outerplanar graphs, Discrete Applied Mathematics, vol.2, issue.3, pp.185-191, 1980.

G. Federickson, Fast algorithms for shortest paths in planar graphs, with applications, SIAM Journal on Computing, vol.16, issue.6, pp.1004-1022, 1987.

P. Gawrychowski, H. Kaplan, S. Mozes, M. Sharir, and O. Weimann, Voronoi diagrams on planar graphs, and computing the diameter in deterministicÕ(n 5/3 ) time, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp.495-514, 2018.

M. Habib, R. Mcconnell, C. Paul, and L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, vol.234, issue.1-2, pp.59-84, 2000.

S. Har-peled, Approximating Spanning Trees with Low Crossing Number, 2009.

S. Har-peled and K. Quanrud, Approximation algorithms for polynomial-expansion and lowdensity graphs, SIAM Journal on Computing, vol.46, issue.6, pp.1712-1744, 2017.

D. Haussler and E. Welzl, ?-nets and simplex range queries. Discrete & Computational Geometry, vol.2, pp.127-151, 1987.

M. Henzinger, P. Klein, S. Rao, and S. Subramanian, Faster shortest-path algorithms for planar graphs, Journal of computer and system sciences, vol.55, issue.1, pp.3-23, 1997.

K. Kawarabayashi, P. N. Klein, and C. Sommer, Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs, Automata, Languages and Programming -38th International Colloquium, ICALP 2011, vol.6755, pp.135-146, 2011.

K. Kawarabayashi and B. Reed, A separator theorem in minor-closed classes, 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp.153-162, 2010.

J. Kleinberg, Detecting a network failure, Internet Mathematics, vol.1, issue.1, pp.37-55, 2004.

E. Kranakis, D. Krizanc, B. Ruf, J. Urrutia, and G. Woeginger, The VC-dimension of set systems defined by graphs, Discrete Applied Mathematics, vol.77, issue.3, pp.237-257, 1997.

J. Li and M. Parter, Planar diameter via metric compression, STOC, pp.152-163, 2019.

R. Lipton and R. Tarjan, A separator theorem for planar graphs, SIAM Journal on Applied Mathematics, vol.36, issue.2, pp.177-189, 1979.

J. Matou?ek, Spanning trees with low crossing number, vol.25, pp.103-123, 1991.

J. Matousek, Bounded VC-dimension implies a fractional Helly theorem. Discrete & Computational Geometry, vol.31, pp.251-255, 2004.

J. Ne?et?il and P. Ossona-de-mendez, Sparsity: graphs, structures, and algorithms, vol.28, 2012.

J. Ne?et?il and P. Ossona-de-mendez, Structural sparsity, Russian Mathematical Surveys, vol.71, issue.1, p.79, 2016.

S. Olariu, A simple linear-time algorithm for computing the center of an interval graph, International Journal of Computer Mathematics, vol.34, issue.3-4, pp.121-128, 1990.

C. Papadimitriou and M. Yannakakis, On limited nondeterminism and the complexity of the VC dimension, Journal of Computer and System Sciences, vol.53, issue.2, pp.161-170, 1996.

S. Plotkin, S. Rao, and W. Smith, Shallow Excluded Minors and Improved Graph Decompositions, SODA, vol.90, pp.462-470, 1994.

L. Roditty, V. , and V. Williams, Fast approximation algorithms for the diameter and radius of sparse graphs, STOC, pp.515-524, 2013.

N. Sauer, On the density of families of sets, Journal of Combinatorial Theory, Series A, vol.13, issue.1, pp.145-147, 1972.

S. Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific Journal of Mathematics, vol.41, issue.1, pp.247-261, 1972.

V. Vapnik and A. Chervonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Measures of complexity, pp.11-30, 2015.

E. , On spanning trees with low crossing numbers, Data structures and efficient algorithms, pp.233-249, 1992.

C. Wulff-nilsen, Separator theorems for minor-free and shallow minor-free graphs with applications, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), pp.37-46, 2011.