Faster diameter computation in graphs of bounded Euler genus Thanks: K.K. and Ma.P. are supported by Polish National Science Centre SONATA BIS-12 grant number 2022/46/E/ST6/00143. This work is a part of project BOBR (Mi.P., G.S.) that has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 948057). In particular, a majority of work on this manuscript was done while G.S. was affiliated with University of Warsaw. Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, Giannos Stamoulis Abstract We show that for any fixed integer k ⩾ 0 k\geqslant 0 , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n n -vertex graph of Euler genus at most k k in time 𝒪 k ​ ( n 2 − 1 25 ) . \mathcal{O}_{k}(n^{2-\frac{1}{25}}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k k after deletion of at most k k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪 k ​ ( n 2 − 1 356 ​ log 6 ​ k ​ n ) . \mathcal{O}_{k}(n^{2-\frac{1}{356}}\log^{6k}n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K h K_{h} -minor-free graphs, but the running time bound is 𝒪 h ​ ( n 2 − c h ) \mathcal{O}_{h}(n^{2-c_{h}}) for some constant c h > 0 c_{h}>0 depending on h h . That is, our savings in the exponent, as compared to the naive quadratic algorithm, are independent of the parameter k k . The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus. 1 Introduction Computing the diameter of an input (undirected, unweighted) graph G is a classic computational problem that can be trivially solved in \mathcal{O}(nm) time 1 1 1 We follow the convention that the vertex and the edge count of the input graph are denoted by n and m , respectively. . In 2013, Roditty and Vassilevska-Williams showed that this running time bound cannot be significantly improved in general: any algorithm distinguishing graphs of diameter 2 and 3 running in time \mathcal{O}(m^{2-\varepsilon}) , for any fixed \varepsilon>0 , would break the Strong Exponential Time Hypothesis [ 14 ] . This motivates the search for restrictions on G that would make the problem of computing the diameter more tractable. As shown by Cabello and Knauer [ 3 ] , sophisticated orthogonal range query data structures allow near-linear diameter computation in graphs of constant treewidth. A breakthrough result by Cabello [ 2 ] showed that the diameter of an n -vertex planar graph can be computed in \widetilde{\mathcal{O}}(n^{11/6}) time; this complexity has been later improved by Gawrychowski, Kaplan, Mozes, Sharir, and Weimann to \widetilde{\mathcal{O}}(n^{5/3}) [ 8 ] 2 2 2 The \widetilde{\mathcal{O}}(\cdot) notation hides factors polylogarithmic in n , and the \mathcal{O}_{k}(\cdot) notation hides factors depending on a parameter k . . A subsequent line of research [ 5 , 6 , 11 ] generalized this result to K_{h} -minor-free graphs: for every integer h , there exists a constant c_{h}>0 such that the diameter problem in n -vertex K_{h} -minor-free graphs can be solved in time \mathcal{O}_{h}(n^{2-c_{h}}) . In the works [ 6 , 11 ] , it holds that c_{h}=\Omega\left(\frac{1}{h}\right) ; so the savings tend to zero as the size of the excluded clique minor increases. However, known lower bounds, including the one of [ 14 ] , does not exclude the possibility that c_{h} can be made a universal constant. That is, no known lower bound refutes the following conjecture: Conjecture 1.1 . There exists a constant c>0 such that, for every integer h>1 , the diameter problem in (unweighted, undirected) n -vertex K_{h} -minor-free graphs can be solved in time \mathcal{O}_{h}(n^{2-c}) . Graphs of bounded Euler genus. Our main result is the verification of Conjecture 1.1 for graphs of bounded Euler genus. Furthermore, our algorithm computes also the eccentricies of all the vertices of the input graph G . Recall here that the eccentricity of a vertex v\in V(G) is defined as \mathrm{ecc}(v)\coloneqq\max_{u\in V(G)}\mathrm{dist}_{G}(u,v) , where \mathrm{dist}_{G}(\cdot,\cdot) is the distance metric in G . Theorem 1.2 . For every integers k\geqslant 1 , there exists an algorithm that, given an (unweighted, undirected) n -vertex graph G of Euler genus at most k , runs in time \mathcal{O}_{k}(n^{2-\frac{1}{25}}) and computes the diameter of G and the eccentricity of every vertex of G . We remark that in [ 2 , Section 9] , Cabello briefly speculated that his approach could be also generalized to graphs embeddable on surfaces of bounded genus. However, as noted in [ 2 ] , this would require significant effort, as the technique works closely on the embedding and in surfaces of higher genus, additional topological hurdles arise. In contrast, in our proof of Theorem 1.2 the main ingredient is an improved combinatorial bound on the number of so-called distance profiles [ 11 ] in graphs of bounded Euler genus. This proof uses topology only very lightly, while the rest of the argument is rather standard and topology-free. All in all, we obtain a robust methodology of approaching the problem, which, as we will see, can be also used to attack Conjecture 1.1 to some extent. To explain our bound on distance profiles, we need to recall several relevant definitions. Let G be a graph, R\subseteq V(G) be a subset of vertices, and s_{R}\in R be a vertex in R . The distance profile of a vertex u\in V(G) to R (relative to s_{R} ) is the function \mathrm{prof}_{R,s_{R}}[u]\colon R\to\mathbb{Z} defined as follows: \mathrm{prof}_{R,s_{R}}[u](s)=\mathrm{dist}_{G}(u,s)-\mathrm{dist}_{G}(u,s_{R})\qquad\textrm{for all }s\in R. Note that provided R is connected 3 3 3 A subset of vertices R of a graph G is connected if the induced subgraph G[R] is connected. , we have \mathrm{prof}_{R,s_{R}}[u](s)\in\{-|R|,-|R|+1,\ldots,|R|-1,|R|\} . In [ 11 ] , Le and Wulff-Nilsen proved that if R is connected and G is K_{h} -minor-free, then the set system \left\{\left\{(s,i)\in R\times\{-|R|,\ldots,|R|\}~|~i\leqslant\mathrm{prof}_{R,s_{R}}[u](s)\right\}~\colon~u\in V(G)\right\} has VC dimension at most h-1 . Hence, by applying the Sauer-Shelah Lemma we obtain that Theorem 1.3 ( [ 11 ] ) . For every integer h\geqslant 1 , K_{h} -minor-free graph G , connected set R\subseteq V(G) , and s_{R}\in R , there are at most \mathcal{O}_{h}(|R|^{2h-2}) different distance profiles to R relative to s_{R} . The VC dimension argument applied above inevitably leads to a bound with the exponent depending on h . We show that for graphs of bounded Euler genus, the bound of Theorem 1.3 can be improved to a polynomial of degree independent of the parameter. Theorem 1.4 . For every integer k\geqslant 1 , (unweighted, undirected) graph G of Euler genus at most k , connected set R\subseteq V(G) , and s_{R}\in R , the number of distance profiles to R relative to s_{R} is at most \mathcal{O}_{k}(|R|^{12}) . The main idea behind the proof of Theorem 1.4 is the following simple observation: if P is a shortest path from some u\in V(G) to s_{R} , then, as one walks along P from u to s_{R} , the distance profile of the current vertex to R can only (point-wise) increase. A slightly more technical modification of this argument works for shortest paths from u\in V(G) to R . This allows us to reduce the case of bounded Euler genus graphs to the planar case by cutting along a constant number of shortest-to- R paths, and analysing how the distance profiles change during such a process. One could ask whether an improvement similar to that of Theorem 1.4 would be possible even in the generality of K_{h} -minor-free graphs. Unfortunately, it seems that Theorem 1.4 is the limit of such improvements. More precisely, the following simple example shows that the linear dependency on h in the exponent of the bound on the number of profiles is inevitable even in graphs of treewidth h (which are K_{(h+1)^{2}} -minor-free). Let 00 . Then we use Theorem 1.4 for individual regions R to speed up the computation of distances between R and V(G)-R , by grouping vertices outside R according to their distance profiles to R . Each group is batch-processed in a single step. Generalizations. Further, we show that our techniques combine well with the techniques for bounded treewidth graphs of Cabello and Knauer [ 3 ] . First, we show that Conjecture 1.1 holds for classes of graphs of bounded Euler genus with a constant number of apices , i.e., vertices that are arbitrarily connected to the rest of the graph. Theorem 1.5 . For every integers g,k\geqslant 1 , there exists an algorithm that, given an (unweighted, undirected) n -vertex graph G and a set A\subseteq V(G) such that |A|\leqslant k and G-A is of Euler genus at most g , runs in time \mathcal{O}_{g,k}(n^{2-\frac{1}{25}}\log^{k-1}n) and computes the diameter of G and the eccentricity of every vertex of G . Second, we show that Conjecture 1.1 holds for classes of graphs constructed by clique-sums of graphs as in Theorem 1.5 . To state this result formally, we need some definitions. For a graph G , a tree decompostion of G is a pair (T,\beta) where T is a tree and \beta is a function that assigns to every t\in V(T) a bag \beta(t)\subseteq V(G) such that (1) for every v\in V(G) , the set \{t\in V(T)~|~v\in\beta(t)\} is nonempty and connected in T , and (2) for every uv\in E(G) there exists t\in V(T) with u,v\in\beta(t) . The torso of the bag \beta(t) is constructed from G[\beta(t)] by adding, for every neighbor s of t in T , all edges between the vertices of \beta(s)\cap\beta(t) . Theorem 1.6 . For every integer k\geqslant 1 , there exists an algorithm with the following specification. The input consists of an (unweighted, undirected) n -vertex graph G together with a tree decomposition (T,\beta) of G and a set A(t)\subseteq\beta(t) for every t\in V(T) satisfying the following properties: • For every node t\in V(T) , we have that |A(t)|\leqslant k and the torso of \beta(t) with the vertices of A(t) deleted is a graph of Euler genus at most k . • For every edge st\in E(T) , we have |\beta(s)\cap\beta(t)|\leqslant k . The algorithm runs in time \mathcal{O}_{k}(n^{2-\frac{1}{356}}\log^{6k}n) and computes the diameter of G and the eccentricity of every vertex of G . Note that the statements of Theorems 1.5 and 1.6 require the set A and the decomposition (T,\beta) , respectively, to be provided explicitly on input; this should be compared with more general statements where the algorithm is given only G with a promise that such set A or decomposition (T,\beta) exist. At this point, we are not aware of any existing algorithm that would find in subquadratic time a set A as in Theorem 1.5 , or the decomposition (T,\beta) with the sets A as in Theorem 1.6 , even in the approximate sense. However, we were informed by Korhonen, Pilipczuk, Stamoulis, and Thilikos [ 10 ] that it seems likely that the techniques introduced in the recent almost linear-time algorithm for minor-testing [ 9 ] could be used to construct such an algorithm, with almost linear time complexity. With this result in place, the assumption about the decomposition and/or apex sets being provided on input could be lifted in Theorems 1.5 and 1.6 ; this is, however, left to future work. Discussion. As one of the main outcomes of their theory of graph minors, Robertson and Seymour proved the following Structure Theorem [ 13 ] : every K_{h} -minor-free graph G admits a tree decomposition (T,\beta) such that • for every pair s,t of adjacent nodes of T , the set \beta(t)\cap\beta(s) has size \mathcal{O}_{h}(1) ; and • the torso of every bag \beta(t) is “nearly embedable” into a surface of bounded (in terms of h ) Euler genus. The notion of being “nearly embeddable” encompasses adding a constant number of apices (which can be handled by Theorem 1.6 ) and a constant number of so-called vortices (which are not handled by Theorem 1.6 ). Thus, our methods fall short of verifying Conjecture 1.1 in full generality due to vortices. We remark that recently, Thilikos and Wiederrecht [ 18 ] proved a variant of the Structure Theorem, where under the stronger assumption of excluding a minor of a shallow vortex grid , instead of a clique minor, they gave a decomposition as above, but with torsos devoid of vortices. Thus, the decomposition for shallow-vortex-grid-minor-free graphs provided by [ 18 ] can be directly plugged into Theorem 1.6 , with the caveat that [ 18 ] does not provide a subquadratic algorithm to compute the decomposition. Coming back to Conjecture 1.1 , the simplest case that we are currently unable to solve is the setting when the input is a planar graph plus a single vortex. More formally, for a fixed integer k , let \mathcal{G}_{k} be the class of graphs defined as follows. We have G\in\mathcal{G}_{k} if there exist two subgraphs G_{0},G_{1} of G and a sequence of vertices v_{1},\ldots,v_{b} in V(G_{0})\cap V(G_{1}) such that: • V(G)=V(G_{0})\cup V(G_{1}) , • E(G)=E(G_{0})\cup E(G_{1}) , • G_{0} admits a planar embedding where the vertices v_{1},\ldots,v_{b} lie on one face in this order, and • G_{1} admits a tree decomposition (T_{1},\beta_{1}) , where T_{1} is a path on nodes t_{1},\ldots,t_{b} and for every i\in\{1,\ldots,b\} , the bag \beta_{1}(t_{i}) contains v_{i} and is of size at most k . It is easy to see that graphs from \mathcal{G}_{k} are K_{k+\mathcal{O}(1)} -minor-free. Do they satisfy Conjecture 1.1 ? That is, is there a constant c>0 such that the diameter problem in \mathcal{G}_{k} can be solved in time \mathcal{O}_{k}(n^{2-c}) ? Organization. We prove Theorem 1.4 in Section 3 . Theorem 1.5 is proven in Section 4 ; note that Theorem 1.2 follows from Theorem 1.5 for k=1 . Theorem 1.6 is proven in Section 5 . 2 Preliminaries Set systems and VC-dimension. A set system is a collection \mathcal{F} of subsets of a given set A , which we call ground set of \mathcal{F} . We say that a subset Y\subseteq A is shattered by \mathcal{F} if \{Y\cap S:S\in\mathcal{F}\}=2^{Y} , that is, the intersections of Y and the sets in \mathcal{F} contain every subset of Y . The VC-dimension of a set system \mathcal{F} with ground set A is the size of the largest subset Y\subseteq A shattered by \mathcal{F} . The notion of VC-dimension was introduced by Vapnik and Chervonenkis [ 19 ] . We will use the following well-known Sauer-Shelah Lemma [ 15 , 16 ] , which gives a polynomial upper bound on the size of a set system of bounded VC-dimension. Lemma 2.1 (Sauer-Shelah Lemma) . Let \mathcal{F} be a set system with ground set A . If the VC-dimension of \mathcal{F} is at most k , then |\mathcal{F}|=\mathcal{O}(|A|^{k}) . Basic graph notation. All our graphs are undirected. For a graph G , the neighborhood of a vertex u is defined as N_{G}(u)=\{v~\colon~uv\in E(G)\} and for X\subseteq V(G) we have N_{G}(X)=\bigcup_{u\in X}N_{G}(u)-X . The length of a path P , denoted |P| , is the number of edges of P . For two vertices u,v of a graph G , the distance between u and v , denoted \mathrm{dist}_{G}(u,v) , is defined as the minimum length of a path in G with endpoints u and v . For every v\in V(G) and set R\subseteq V(G) , we set \mathrm{dist}_{G}(v,R)\coloneqq\min\{\mathrm{dist}_{G}(v,y)\colon y\in R\}. For vertices x,y appearing on a path P , by P[x,y] we denote the subpath of P with endpoints x and y . The set of vertices traversed by a path P is denoted by V(P) . In all above notation, we sometimes drop the subscript if the graph is clear from the context. For a nonnegative integer q , we use the shorthand [q]\coloneqq\{1,\ldots,q\} . For a vertex v\in V(G) and a set X\subseteq V(G) , we define the X -eccentricity of v as \mathrm{ecc}_{X}(v)\coloneqq\max_{x\in X}\mathrm{dist}(v,x) . Thus, the eccentricity of v in G is the same as its V(G) -eccentricity. The Euler genus of a graph G is the minimum Euler characteristic of a surface, where G is embeddable. We refer to the textbook of Mohar and Thomassen for more on surfaces and embedded graphs [ 12 ] . We will use the following result of Le and Wulff-Nilsen [ 11 , Theorem 1.3] for planar graphs. Note that the set R is not necessarily connected. Theorem 2.2 . Let h\geqslant 1 be an integer, G be a K_{h} -minor-free (unweighted, undirected) graph, R be a subset of V(G) , and s_{R}\in R . Then the set system \left\{\left\{(s,i)\in R\times\mathbb{Z}~|~i\leqslant\mathrm{dist}_{G}(u,s)-\mathrm{dist}_{G}(u,s_{R})\right\}~\colon~u\in V(G)\right\} has VC-dimension at most h-1 . Algorithmic tools. All our algorithms assume the word RAM model. To cope with apices, we will need the following classic data structure due to Willard [ 20 ] . Theorem 2.3 ( [ 20 ] ) . Let V be a set of n points in \mathbb{R}^{d} and let w\colon V\to\mathbb{R} be a weight function. By a suffix range , we mean any set of the form \mathsf{Range}(r_{1},\ldots,r_{d})\coloneqq\{(x_{1},\dots,x_{d})\in\mathbb{R}^{d}\,\mid\,x_{i}\geqslant r_{i}\textrm{ for all }i\in[d]\} for some range parameters r_{1},\ldots,r_{d}\in\mathbb{R} . There is a data structure that uses \mathcal{O}\left(n\log^{d-1}n\right) preprocessing time, \mathcal{O}\left(n\log^{d-1}n\right) memory and answers the following suffix range queries in time \mathcal{O}\left(\log^{d-1}n\right) : given a tuple (r_{i})_{i\in[d]} , find the maximum value of w(v) over all v\in V\cap\mathsf{Range}(r_{1},\ldots,r_{d}) . We will also need the following standard statement about r -divisions. Theorem 2.4 ( [ 21 ] ) . Let G be a K_{t} -minor-free graph on n vertices. For any fixed constant \varepsilon>0 , and for any parameter r with Ct^{2}\log n\leqslant r\leqslant n , where C is some absolute constant, we can construct in time \mathcal{O}\left(n^{1+\varepsilon}\sqrt{r}\right) an r -division of G , that is, a collection \mathcal{R} of connected subsets of vertices of G such that: • \bigcup\mathcal{R}=V(G) , • |R|\leqslant r for every R\in\mathcal{R} , and • \sum_{R\in\mathcal{R}}|\partial R|\leqslant\mathcal{O}(nt/\sqrt{r}) , where \partial R=R\cap N_{G}(V(G)-R) . 3 Distance profiles in graphs of bounded Euler genus In this section we prove Theorem 1.4 . Our argument consists of a reduction to the planar case, where we can use the constant bound on the VC-dimension of the set system given by the distance profiles due to Le and Wulff-Nilsen [ 11 ] . The main idea behind the reduction is to consider certain notions of “extended” profiles, where the extension is built along a collections of shortest paths. These shortest paths can be chosen in such a way that by cutting the graph along these paths we obtain a plane graph. Then a bound on the number of the extended profiles in the obtained plane graph translates to a bound on the number of (standard) distance profiles in the original graph. Preliminary definitions and results needed for defining profiles with respect to shortest paths are given in Section 3.1 . These extended profiles are then defined in Section 3.2 . There, we also prove that a fundamental lemma that equality of extended profiles entails equality of (standard) distance profiles. The main reduction providing the proof of Theorem 1.4 is given at the end of this section. 3.1 Milestones Let G be a graph, R be a subset of V(G) , v_{0} be a vertex in V(G) , and P be a shortest path from v_{0} to R . Let x be the unique vertex in V(P)\cap R . Further, let \leqslant_{P} be the linear ordering of the vertices traversed by P : for two vertices v,u\in V(P) , we have v\leqslant_{P}u if u belongs to P[v,x] . We say that a vertex v\in V(P) is a milestone of P if either v=x or we have \mathrm{prof}_{R,x}[v]\neq\mathrm{prof}_{R,x}[u] , where u is the successor of v in \leqslant_{P} . We denote by M_{R}(P) the set of all milestones of P . Given a milestone v\in M_{R}(P) , the neutral prefix of v in P is defined as the vertex set of the maximal subpath Q of P[v_{0},v] satisfying the following: v is the only milestone of P that belongs to Q . The next lemma shows that minimum-length paths towards R that contain a vertex in the neutral prefix of a milestone can be assumed to pass through that milestone vertex. Lemma 3.1 . Let G be a graph, R be a subset of V(G) , v_{0} be a vertex in V(G) and P be a shortest path from v_{0} to R . Then for every v\in M_{R}(P) , every u in the neutral prefix of v , and every y\in R , it holds that \mathrm{dist}(u,y)=|P[u,v]|+\mathrm{dist}(v,y) . Proof. Let x be the unique vertex of V(P)\cap R . Note that, by definition, \mathrm{prof}_{R,x}[v]=\mathrm{prof}_{R,x}[u] . Also, \mathrm{dist}(u,x)=\mathrm{dist}(u,v)+\mathrm{dist}(v,x) and \mathrm{dist}(u,v)=|P[u,v]| . Therefore, \mathrm{dist}(u,y)=|P[u,v]|+\mathrm{dist}(v,y) for every y\in R . ∎ We also give an upper bound on the number of milestones. Lemma 3.2 . Let G be a graph, R be a connected subset of V(G) , v_{0} be a vertex of G , and P be a shortest path from v_{0} to R . Then the number of milestones of P is at most |R|^{2}+1 . Proof. Let x be the unique vertex of V(P)\cap R . First observe that since P is a shortest path from v_{0} to R , we have \mathrm{dist}(v,y)\geqslant\mathrm{dist}(v,x) for every v\in V(P) and every y\in R ; hence \mathrm{prof}_{R,x}[v](y)\geqslant 0 . Also, since R is connected, for every y\in R we have \mathrm{prof}_{R,x}[x](y)\leqslant|R| . To conclude the proof, it suffices to prove that for all v_{1},v_{2}\in V(P) with v_{1}\leqslant_{P}v_{2} , we have \mathrm{prof}_{R,x}[v_{1}](y)\leqslant\mathrm{prof}_{R,x}[v_{2}](y)\qquad\textrm{for all }y\in R. (1) Indeed, ( 1 ) together with the previous observations shows that all the distinct distance profiles of the form \mathrm{prof}_{R,x}[v] for v\in V(P) can be treated as vectors of length |R| with entries in \{0,\ldots,|R|\} , and they all have distinct sums \sum_{y\in R}\mathrm{prof}_{R,x}[v](y) . Since these sums range between 0 and |R|^{2} , the total number of distinct profiles is at most |R|^{2}+1 , implying the same bound on the number of milestones. To see why ( 1 ) holds, note that \mathrm{dist}(v_{1},y)\leqslant\mathrm{dist}(v_{1},v_{2})+\mathrm{dist}(v_{2},y) implies that \mathrm{dist}(v_{1},y)\leqslant\mathrm{dist}(v_{1},v_{2})+\mathrm{prof}_{R,x}[v_{2}](y)+\mathrm{dist}(v_{2},x)=\mathrm{prof}_{R,x}[v_{2}](y)+\mathrm{dist}(v_{1},x); the last equality follows from P being a shortest path containing v_{1},v_{2}, and x (in this order). This in turn implies that \mathrm{prof}_{R,x}[v_{1}](y)=\mathrm{dist}(v_{1},y)-\mathrm{dist}(v_{1},x)\leqslant\mathrm{prof}_{R,x}[v_{2}](y) , as claimed. ∎ 3.2 Anchor-distance profiles Shortest path collections. Let G be a graph and R be a subset of vertices of G . We say that a collection \mathcal{P} of paths in G is an R -shortest path collection if • every P\in\mathcal{P} is a shortest path from some v^{P}\in V(G) to R , i.e., |P|=\mathrm{dist}(v^{P},R) ; and • R\subseteq\bigcup_{P\in\mathcal{P}}V(P) . For each P\in\mathcal{P} , we denote by x^{P} the endpoint of P in R . Note that the collection \mathcal{P} obtained by taking, for every y\in R , the zero-length path from y to y , is an R -shortest path collection. We say that an R -shortest path collection is consistent if, for every P_{1},P_{2}\in\mathcal{P} and v\in V(P_{1})\cap V(P_{2}) the paths P_{1}[v,x^{P_{1}}] and P_{2}[v,x^{P_{2}}] are equal. That is, once two paths intersect, they continue together towards R . The following statement is a direct consequence of the definition of an R -shortest path collection. Observation 3.1 . Let G be a graph, R be a subset of vertices of G , and \mathcal{P} be an R -shortest path collection. Then for every two paths P_{1},P_{2}\in\mathcal{P} and every v\in V(P_{1})\cap V(P_{2}) , we have |P_{1}[v,x^{P_{1}}]|=|P_{2}[v,x^{P_{2}}]| . Anchor vertices and their prefixes. Let G be a graph, R be a subset of V(G) , and \mathcal{P} be an R -shortest path collection. We denote by H_{\mathcal{P}} the union of the paths in \mathcal{P} , i.e., the graph (\bigcup_{P\in\mathcal{P}}V(P),\bigcup_{P\in\mathcal{P}}E(P)) . We say that a vertex is an anchor vertex if either it has degree more than two in H_{\mathcal{P}} or it is a milestone of a path P\in\mathcal{P} . We denote by A_{R}(P) the set of all anchor vertices lying on a path P\in\mathcal{P} and by A_{R}(\mathcal{P}) the set of all anchor vertices for \mathcal{P} . Given a path P\in\mathcal{P} with endpoints v_{0} and y\in R , and an anchor vertex w\in A_{R}(P) , the prefix of w in P is the vertex set of the maximal subpath Q of P[v_{0},v] satisfying the following: v is the only anchor vertex of P that belongs to Q . Note that for every anchor w\in V(P) there is a milestone w^{\prime} of P (possibly w=w^{\prime} ) such that the prefix of w in P is a subset of the neutral prefix of w^{\prime} in P . Finally, for an anchor vertex w , the tail of w , denoted \mathrm{tail}(w) , is the subgraph of G consisting of the union of all prefixes of w in P over all paths P\in\mathcal{P} that contain w . Hat-distances. Let G be a graph, R be a subset of vertices of G , and \mathcal{P} be an R -shortest path collection. We denote by U_{\mathcal{P}}\coloneqq V(G)-\bigcup_{P\in\mathcal{P}}V(P). For every u\in U_{\mathcal{P}} , and every anchor vertex w\in A_{R}(\mathcal{P}) , we set \widehat{\mathrm{dist}}(u,w)\coloneqq\min\{|Q_{u,z}|+|P[z,w]|\colon P\in\mathcal{P}\wedge w\in V(P)\wedge z\text{ is in the prefix of $w$ in $P$}\}, where Q_{u,z} is a shortest path from u to z with all its internal vertices in U_{\mathcal{P}} . If such Q_{u,z} does not exist for any z\in V(\mathrm{tail}(w)) , we set \widehat{\mathrm{dist}}(u,w)\coloneqq\infty . The following statement is a direct consequence of the definition of \widehat{\mathrm{dist}}(\cdot,\cdot) . Observation 3.2 . Let G be a graph, R be a subset of vertices of G , and \mathcal{P} be an R -shortest path collection. Then for every u\in U_{\mathcal{P}} , we have that \mathrm{dist}(u,R)=\min\left\{\widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,R)\colon w\in A_{R}(\mathcal{P})\right\}. Anchor-distance profiles. Let G be a graph, R be a subset of vertices of G , and \mathcal{P} be an R -shortest path collection. The anchor-distance profile of a vertex u\in U_{\mathcal{P}} to R with respect to \mathcal{P} is a function \mathrm{prof}^{\star}_{R,\mathcal{P}}[u] mapping each w\in A_{R}(\mathcal{P}) to \mathrm{prof}^{\star}_{R,\mathcal{P}}[u](w)\coloneqq\widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,R)-\mathrm{dist}(u,R). Observation 3.2 implies that we always have \mathrm{prof}^{\star}_{R,\mathcal{P}}[u](w)\geqslant 0 . We set \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u](w)\coloneqq\min\{\mathrm{prof}^{\star}_{R,\mathcal{P}}[u](w),|R|+1\}. Lemma 3.3 . Let G be a graph, let R be a connected subset of vertices of G , and s_{R}\in R . Also, let \mathcal{P} be an R -shortest path collection. Then for all u_{1},u_{2}\in U_{\mathcal{P}} , \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u_{1}]=\widehat{\mathrm{prof}}_{R,\mathcal{P}}[u_{2}]\qquad\textrm{implies}\qquad\mathrm{prof}_{R,s_{R}}[u_{1}]=\mathrm{prof}_{R,s_{R}}[u_{2}]. Proof. Fix u_{1},u_{2}\in U_{\mathcal{P}} with \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u_{1}]=\widehat{\mathrm{prof}}_{R,\mathcal{P}}[u_{2}] . We start by proving the following. Claim 3.1 . Let u\in U_{\mathcal{P}} and y\in R . There is an anchor w\in A_{R}(\mathcal{P}) such that • \widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,y)=\mathrm{dist}(u,y) and • \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u](w)\leqslant|R| . Proof. Let Q be a shortest path from u to y and let P\in\mathcal{P} be the path which Q first intersects (if the first vertex of Q in \bigcup_{P\in\mathcal{P}}V(P) belongs to more than one paths in \mathcal{P} , we choose P arbitrarily among these paths). Also, let u^{\prime} be the first vertex of Q (when ordering from u to y ) in V(P) and w be the anchor of P that contains u^{\prime} in its prefix (in P ). Note that u^{\prime}\in V(\mathrm{tail}(w)) . We first show that \widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,y)=\mathrm{dist}(u,y). (2) By Lemma 3.1 and the fact that |Q[u^{\prime},y]|=\mathrm{dist}(u^{\prime},y) , we have \mathrm{dist}(w,y)=|Q[u^{\prime},y]|-|P[u^{\prime},w]|. (3) Also, by definition, we have \widehat{\mathrm{dist}}(u,w)\leqslant|Q[u,u^{\prime}]|+|P[u^{\prime},w]|. (4) By ( 3 ) and ( 4 ), we get that \widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,y)\leqslant|Q| . Moreover, since Q is a shortest path from u to y and \widehat{dist}(u,w)\geqslant\mathrm{dist}(u,w) , we have |Q|=\mathrm{dist}(u,y)\leqslant\mathrm{dist}(u,w)+\mathrm{dist}(w,y)\leqslant\widehat{dist}(u,w)+dist(w,y). This proves ( 2 ). Next, we show that \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u](w)\leqslant|R| . Note that \displaystyle\mathrm{prof}^{\star}_{R,\mathcal{P}}[u](w)+\mathrm{dist}(u,R) \displaystyle=\widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,R) \displaystyle\leqslant\widehat{\mathrm{dist}}(u,w)+\mathrm{dist}(w,y)=\mathrm{dist}(u,y). The connectivity of R implies that \mathrm{dist}(u,y)\leqslant\mathrm{dist}(u,R)+|R| , which gives \mathrm{prof}^{\star}_{R,\mathcal{P}}[u](w)\leqslant|R| , and the claim follows. ∎ We next show that there is an integer c such that for every y\in R , we have \mathrm{dist}(u_{1},y)=\mathrm{dist}(u_{2},y)+c. Note that this will immediately imply that \mathrm{prof}_{R,s_{R}}[u_{1}]=\mathrm{prof}_{R,s_{R}}[u_{2}] . By Observation 3.2 , for every h\in\{1,2\} , there is an anchor w_{h}\in A_{R}(\mathcal{P}) such that \mathrm{dist}(u_{h},R)=\widehat{\mathrm{dist}}(u_{h},w_{h})+\mathrm{dist}(w_{h},R) , which is equivalent to \mathrm{prof}^{\star}_{R,\mathcal{P}}[u_{h}](w_{h})=0 . If w_{h} lies on P_{h}\in\mathcal{P} , then \mathrm{dist}(u_{h},R)=\mathrm{dist}(u_{h},x^{P_{h}}) . Therefore, as \mathrm{prof}^{\star}_{R,\mathcal{P}}[u_{1}]=\mathrm{prof}^{\star}_{R,\mathcal{P}}[u_{2}] , we can choose w_{1}=w_{2} and P_{1}=P_{2} , hence x^{P_{1}}=x^{P_{2}} . In other words, there exists x\in R such that \mathrm{dist}(u_{1},R)=\mathrm{dist}(u_{1},x) and \mathrm{dist}(u_{2},R)=\mathrm{dist}(u_{2},x) . We set c\coloneqq\mathrm{dist}(u_{1},x)-\mathrm{dist}(u_{2},x)=\mathrm{dist}(u_{1},R)-\mathrm{dist}(u_{2},R) . Now, fix y\in R . Let w_{1}\in A_{R}(P) be the anchor from Claim 3.1 (applied for u_{1} and y ). As \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u_{1}]=\widehat{\mathrm{prof}}_{R,\mathcal{P}}[u_{2}] and \mathrm{prof}^{\star}_{R,\mathcal{P}}[u_{1}](w_{1})\leqslant|R| , we have \mathrm{prof}^{\star}_{R,\mathcal{P}}[u_{1}](w_{1})=\mathrm{prof}^{\star}_{R,\mathcal{P}}[u_{2}](w_{1}) , i.e., \widehat{\mathrm{dist}}(u_{1},w_{1})+\mathrm{dist}(w_{1},R)-\mathrm{dist}(u_{1},R)=\widehat{\mathrm{dist}}(u_{2},w_{1})+\mathrm{dist}(w_{1},R)-\mathrm{dist}(u_{2},R). Therefore, \displaystyle\mathrm{dist}(u_{1},y) \displaystyle=\widehat{\mathrm{dist}}(u_{1},w_{1})+\mathrm{dist}(w_{1},y) \displaystyle=\widehat{\mathrm{dist}}(u_{2},w_{1})+\mathrm{dist}(w_{1},y)+c\geqslant\mathrm{dist}(u_{2},y)+c; the first equality follows from Claim 3.1 . Thus \mathrm{dist}(u_{2},y)+c\leqslant\mathrm{dist}(u_{1},y) . A symmetric reasoning shows that also \mathrm{dist}(u_{1},y)-c\leqslant\mathrm{dist}(u_{2},y) . Therefore we get \mathrm{dist}(u_{1},y)=\mathrm{dist}(u_{2},y)+c , as required. ∎ 3.3 Reduction from bounded genus graphs to planar graphs We next recall several definitions related to embeddings of graphs on surfaces. Our basic terminology follows [ 12 ] . We say that a graph H embedded in a surface \Sigma is a simple cut-graph of \Sigma if H has a single face that is also homeomorphic to an open disk; equivalently, H has a single facial walk. Given a surface \Sigma and a simple cut-graph H on \Sigma , we denote by \Sigma\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H the surface obtained by cutting \Sigma along H . Note that, provided H is a simple cut-graph, \Sigma\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H is always a disk. Suppose now that a graph G embedded on \Sigma and H is a subgraph of G that is a simple cut-graph of H . We define G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H to be the graph embedded on \Sigma\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H obtained from G as follows. First, let \sigma be the (unique) facial walk of H and note that each edge e of H is contained exactly twice in \sigma and each vertex v of H is contained in \sigma as many times as the degree of v in H . To obtain G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H , we replace H with a simple cycle C_{\sigma} whose vertex set is the set of copies of vertices of H and its edge set is the set of copies of edges of H in the obvious way. Notice that \sigma also prescribes for every edge uv of G between a vertex u\in V(G)-V(H) and a vertex v\in V(H) , to which copy of v in G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H the vertex u should be adjacent to (in G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H ). See Figure 2 for an illustration. Figure 2: Left: A graph G embedded on a surface \Sigma and a subgraph H of G (in blue) that is a simple cut-graph of \Sigma . Right: The graph G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H embedded on the surface \Sigma\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H (which is homeomorphic to a disk); the blue vertices/edges are copies of the vertices/edges of H . We will use the following well-known result which appears in the literature under different formulations; see e.g. [ 1 , 4 , 7 ] . Lemma 3.4 . For every integer k\geqslant 1 and for every edge-weighted connected graph G embedded on a surface \Sigma of Euler genus at most k and every vertex u\in V(G) , there is a subgraph H of G with the following properties: • H is a simple cut-graph of \Sigma , and • V(H) is the union of the vertex sets of \mathcal{O}(k) shortest paths in G that have u as a common endpoint. We are now ready to proceed to the proof of Theorem 1.4 . Employing Lemma 3.3 , we aim at bouding the VC-dimension of the set system defined by the anchor-distance profiles. This is can be done by a suitable reduction to the planar setting using Lemma 3.4 . Proof of Theorem 1.4 . We assume that G is connected – the distance profiles of all vertices that are not connected to R are equal. Let T_{R} be a spanning tree of G[R] and let G_{0} be the graph obtained from G after contracting T_{R} into a single vertex v_{R} . Consider an embedding of G_{0} on a surface \Sigma of Euler genus at most k . By Lemma 3.4 , there is a subgraph H_{0} of G_{0} that is a simple cut-graph of \Sigma and a family \mathcal{P}_{0} of \mathcal{O}(k) shortest paths in G_{0} , each with v_{R} as an endpoint, such that V(H_{0})=\bigcup_{P\in\mathcal{P}_{0}}V(P) . Furthermore, as Lemma 3.4 handles edge weights, we can slightly perturb the weights so that shortest paths in G_{0} are unique and, in particular, all shortest paths with one endpoint in v_{R} form a tree. Since H_{0} is a simple cut-graph of \Sigma , G_{0}\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H_{0} is disk-embedded. Uncontracting T_{R} , we get a subgraph H of G such that G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H is disk-embedded. Let \mathcal{P} be the family of projections of the paths of \mathcal{P}_{0} onto G plus, for every y\in R , a zero-length path from y to y . Hence, \mathcal{P} is an R -shortest paths collection of size \mathcal{O}(k) with V(\mathcal{P})=V(H) . Furthermore, since in G_{0} the paths of \mathcal{P}_{0} formed a tree rooted at v_{R} , \mathcal{P} is consistent. Note that due to Lemma 3.2 we have that \sum_{P\in\mathcal{P}}|M_{R}(P)|\leqslant\mathcal{O}_{k}(|R|^{2}) . Also, since \mathcal{P} is consistent, if B are the vertices that are not in R (recall that vertices in R are milestones) and have degree more than two in the graph obtained by the union of the paths in \mathcal{P} , then |B|\leqslant|\mathcal{P}|-1 . Hence, \sum_{P\in\mathcal{P}}|A_{R}(P)|\leqslant\mathcal{O}_{k}(|R|^{2}). (5) We set \mathcal{T} be the set of all vertices of G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H that are copies of the anchor vertices A_{R}(\mathcal{P}) . Every anchor vertex has \mathcal{O}_{k}(1) copies in \mathcal{Q} and therefore, due to ( 5 ), |\mathcal{T}|=\mathcal{O}_{k}(|R|^{2}). (6) For s\in\mathcal{T} , let w(s)\in A_{R}(\mathcal{R}) be the anchor vertex whose copy (in G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H ) is s . In the other direction, for w\in A_{R}(\mathcal{R}) , let S(w) be the set of copies of w in G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H . Let U be the set of vertices of G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H that are not copies of vertices from H (i.e., U=V(G)-V(H) ). We set E_{\mathsf{out}} be the set of all edges uv of G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H where u\in U and v is a copy of a vertex from H , i.e., v\in V(G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H)-U . We also set E_{\mathsf{next}} be the set of all edges uv of G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H where u is a copy of an anchor vertex w\in A_{R}(P) for some P\in\mathcal{P} and v is a copy of the neighbor of w in P that is not in the prefix of w in P . Let now \widehat{G} be the graph obtained from G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H after the following modifications: • we subdivide |V(G)| -many times each edge in E_{\mathsf{out}}\cup E_{\mathsf{next}} , • we introduce a new vertex t and add, for every s\in\mathcal{T} , a path between t and s of length d_{w(s),t}\coloneqq|V(G)|+\mathrm{dist}_{G}(w(s),R). See Figure 3 . Observe that since G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H is disk-embedded, \widehat{G} is planar, because we may embed t together with all the added paths outside of the disk containing G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H . Figure 3: An illustration of (a part of) the construction of the graph \widehat{G} . The squared vertices are copies of anchor vertices. The marked squared vertex is also a copy of a vertex in R . The highlighted edges are copies of edges of H in G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H , while the paths obtained by subdividing the edges of E_{\mathsf{out}}\cup E_{\mathsf{next}} are depicted with dashed edges. Edges adjacent to t correspond to paths of appropriate length. For every u\in U , we define a function \pi[u] , mapping every w\in A_{R}(\mathcal{P}) to \pi[u](w)\coloneqq\min\{\mathrm{dist}_{\widehat{G}}(u,s):s\in S(w)\}+d_{w,t}-\mathrm{dist}_{\widehat{G}}(u,t). Also, we set \widehat{\mathcal{X}}\coloneqq\{\widehat{X}_{u}\mid u\in U\} , where for u\in U , \widehat{X}_{u}\coloneqq\left\{(w,i)\in A_{R}(\mathcal{P})\times\{0,\ldots,|R|+1\}~|~i\leqslant\pi[u](w)\right\}. Claim 3.2 . The set system \widehat{\mathcal{X}} has size \mathcal{O}_{k}(|R|^{12}) . Proof. We set \mathcal{T}^{+}\coloneqq\mathcal{T}\cup\{t\} . We start with the set system \mathcal{C}^{1}\coloneqq\left\{C_{u}^{1}~\colon~u\in U\right\} , where C_{u}^{1}\coloneqq\left\{(s,i)\in\mathcal{T}^{+}\times\mathbb{Z}~|~i\leqslant\mathrm{dist}_{\widehat{G}}(u,s)-\mathrm{dist}_{\widehat{G}}(u,t)\right\}. As \widehat{G} is planar, by Theorem 2.2 we infer that \mathcal{C} has VC-dimension at most 4. We now “shift columns” of \mathcal{C}^{1} . That is, define \mathcal{C}^{2}\coloneqq\left\{C_{u}^{2}~\colon~u\in U\right\} , where C_{u}^{2}\coloneqq\left\{(s,i)\in\mathcal{T}^{+}\times\mathbb{Z}~|~i\leqslant\mathrm{dist}_{\widehat{G}}(u,s)+d_{w(s),t}-\mathrm{dist}_{\widehat{G}}(u,t)\right\}. Clearly, the VC-dimension of \mathcal{C}^{1} and \mathcal{C}^{2} are equal: a set Z\subseteq\mathcal{T}^{+}\times\mathbb{Z} shatters \mathcal{C}^{1} if and only if the set \{(s,d_{w(s),t}+i)~\colon~(s,i)\in Z\} shatters \mathcal{C}^{2} . Now, let \mathcal{C}^{3} be “cropped” \mathcal{C}^{2} : \mathcal{C}^{3}\coloneqq\left\{C_{u}^{3}~\colon~u\in U\right\} , where C_{u}^{3}\coloneqq C_{u}^{2}\cap\left(\mathcal{T}^{+}\times\{0,\ldots,|R|+1\}\right). Since restricting to a smaller universe cannot increase VC-dimension, \mathcal{C}^{3} has VC-dimension at most 4 . Since |\mathcal{T}^{+}|=\mathcal{O}_{k}(|R|^{2}) , by Sauer-Shelah lemma (Lemma 2.1 ) we have |\mathcal{C}^{3}|=\mathcal{O}_{k}(|R|^{12}) . Now observe that for every u_{1},u_{2}\in U C^{3}_{u_{1}}=C^{3}_{u_{2}}\qquad\mathrm{implies}\qquad\widehat{X}_{u_{1}}=\widehat{X}_{u_{2}}. (7) Indeed, the assumption C^{3}_{u_{1}}=C^{3}_{u_{2}} implies that for every w\in A_{R}(\mathcal{P}) and s\in S(W) we have \displaystyle\max(0,\min(|R|+1,\mathrm{dist}_{\widehat{G}}(u_{1},s)+d_{w,t}-\mathrm{dist}_{\widehat{G}}(u_{1},t))) \displaystyle=\max(0,\min(|R|+1,\mathrm{dist}_{\widehat{G}}(u_{2},s)+d_{w,t}-\mathrm{dist}_{\widehat{G}}(u_{2},t))). For fixed w\in A_{R}(\mathcal{P}) , we take a minimum of the above expression over all s\in S(w) , obtaining: \displaystyle\max(0,\min(|R|+1,\min\{\mathrm{dist}_{\widehat{G}}(u_{1},s)~\colon~s\in S(w)\}+d_{w,t}-\mathrm{dist}_{\widehat{G}}(u_{1},t))) \displaystyle=\max(0,\min(|R|+1,\min\{\mathrm{dist}_{\widehat{G}}(u_{2},s)~\colon~s\in S(w)\}+d_{w,t}-\mathrm{dist}_{\widehat{G}}(u_{2},t))). This proves ( 7 ). From ( 7 ), we infer |\widehat{\mathcal{X}}|\leqslant|\mathcal{C}^{3}|=\mathcal{O}_{k}(|R|^{12}) , as desired. ∎ We next relate the distance from a vertex u\in U to R (in G ) and to t (in \widehat{G} ). Claim 3.3 . For every u\in U , \mathrm{dist}_{G}(u,R)=\mathrm{dist}_{\widehat{G}}(u,t)-2|V(G)| . Proof. Fix u\in U . We first show that \mathrm{dist}_{G}(u,R)\leqslant\mathrm{dist}_{\widehat{G}}(u,t)-2|V(G)| . For this, consider a shortest path \widehat{Q} in \widehat{G} from u to t . Observe that there is a vertex s\in\mathcal{T} that is a copy of an anchor vertex w , such that \widehat{Q}[s,t] is the path from s to t of length d_{w,t} added in the construction of \widehat{G} from G\textrm{\lx@mvs@CutLeft\lx@text@tweaked{xoffset=-0.8em,yoffset=-0.4ex}{\CuttingLine}}H . Recall that d_{w,t}=\mathrm{dist}_{G}(w,R)+|V(G)| . Also, observe that \widehat{Q}[u,s] contains at least one subdivided edge of E_{\mathsf{out}} , as it starts in U and ends outside U , and otherwise corresponds to a walk from u to w in G . Therefore, we have \displaystyle\mathrm{dist}_{\widehat{G}}(u,t)=|\widehat{Q}| \displaystyle=|\widehat{Q}[u,s]|+|\widehat{Q}[s,t]| \displaystyle=|\widehat{Q}[u,s]|+\mathrm{dist}_{G}(w,R)+|V(G)| \displaystyle\geqslant|V(G)|+\mathrm{dist}_{G}(u,w)+\mathrm{dist}_{G}(w,R)+|V(G)| \displaystyle\geqslant\mathrm{dist}_{G}(u,R)+2|V(G)|. We next show that \mathrm{dist}_{G}(u,R)\geqslant\mathrm{dist}_{\widehat{G}}(u,t)-2|V(G)| . For this, consider a shortest path Q in G from u to R . Let y\in R be the unique vertex in R\cap V(Q) . Also, let z be the first vertex of Q (when ordering from u to y ) in \bigcup_{P\in\mathcal{P}}V(P) and let P\in\mathcal{P} be the path that z is contained (if z is contained to more than one paths, pick one of them arbitrarily). Also, let w be the first vertex of P[z,x^{P}] (when ordering from z to x^{P} ) that is an anchor vertex. Observe that Q[u,z] corresponds to a path in \widehat{G} from u to a copy s^{\prime} of z that contains exactly one subdivided edge of E_{\mathsf{out}} (and no edge of E_{\mathsf{next}} ) and there is a copy of P[z,w] in \widehat{G} from s^{\prime} to a copy s of w that contains no edge of E_{\mathsf{out}}\cup E_{\mathsf{next}} . Therefore, \displaystyle|Q| \displaystyle=|Q[u,z]|+|Q[z,y]| \displaystyle=|Q[u,z]|+|P[z,x^{P}]| ​​​( Q[z,y] and P[z,x^{P}] being shortest paths from z to R ) \displaystyle=|Q[u,z]|+|P[z,w]|+|P[w,x^{P}]| \displaystyle=|Q[u,z]|+|P[z,w]|+\mathrm{dist}_{G}(w,R) ( P being shortest path from a vertex v^{P} to R ) \displaystyle\geqslant\mathrm{dist}_{\widehat{G}}(u,s)-|V(G)|+d_{w,t}-|V(G)| \displaystyle\geqslant\mathrm{dist}_{\widehat{G}}(u,t)-2|V(G)|. Thus, we have \mathrm{dist}_{G}(u,R)=|Q|\geqslant\mathrm{dist}_{\widehat{G}}(u,t)-2|V(G)| , as desired. ∎ Claim 3.4 . For every u\in U and w\in A_{R}(\mathcal{P}) , it holds that \displaystyle\widehat{\mathrm{dist}}(u,w)<\infty \displaystyle\quad\mathrm{if\ and\ only\ if}\quad\widehat{\mathrm{dist}}(u,w)=\min\left\{\mathrm{dist}_{\widehat{G}}(u,s)~\colon~s\in S(w)\right\}-|V(G)|,\ \mathrm{and} \displaystyle\widehat{\mathrm{dist}}(u,w)=\infty \displaystyle\quad\mathrm{if\ and\ only\ if}\quad\min\left\{\mathrm{dist}_{\widehat{G}}(u,s)~\colon~s\in S(w)\right\}>2|V(G)|. Proof. We first show that if \widehat{\mathrm{dist}}(u,w)<\infty , then there exists s\in S(w) with \mathrm{dist}_{\widehat{G}}(u,s)\leqslant|V(G)|+\widehat{\mathrm{dist}}(u,w) . To this end, let Q be a path from u to w in G of length \widehat{\mathrm{dist}}(u,w) , as in the definition of \widehat{\mathrm{dist}}(u,w) . There exists P\in\mathcal{P} with w\in A_{R}(P) and a vertex z\in V(P)\cap V(Q) such that Q decomposes into Q[u,z] and Q[z,w]=P[z,w] , with all internal vertices of Q[u,z] in U . Then, \widehat{G} contains a copy s^{\prime} of z such that Q[u,z] projects to a path from u to s^{\prime} with one subdivided edge of E_{\mathsf{out}} (and no edge of E_{\mathsf{next}} ) and also a copy of P[z,w] from s^{\prime} to a copy s of w with no subdivided edge of E_{\mathsf{out}}\cup E_{\mathsf{next}} . The concatenation of these two paths witness that \mathrm{dist}_{\widehat{G}}(u,s)\leqslant|V(G)|+\widehat{\mathrm{dist}}(u,w) , as desired. To finish the proof of the claim, it suffices to show that if there exists s\in S(w) with \mathrm{dist}_{\widehat{G}}(u,s)\leqslant 2|V(G)| , then \widehat{\mathrm{dist}}(u,w)\leqslant\mathrm{dist}_{\widehat{G}}(u,s)-|V(G)| (in particular, \widehat{\mathrm{dist}}(u,w)\neq\infty ). To this end, let \widehat{Q} be a path in \widehat{G} from u to s of minimum length. Since u\in U but s\notin U , \widehat{Q} necessarily contains at least one subdivided edge of E_{\mathsf{out}} . Since |\widehat{Q}|\leqslant 2|V(G)| , \widehat{Q} contains exactly one edge of E_{\mathsf{out}} , no edge of E_{\mathsf{next}} , and no edge incident with t . Consequently, there exists a vertex s^{\prime} on \widehat{Q} which is a copy of a vertex z that lies in the prefix of w on some path P\in\mathcal{P} such that \widehat{Q} decomposes as \widehat{Q}[u,s^{\prime}] , which has all internal vertices in U , and \widehat{Q}[s^{\prime},s] going along a copy of P[z,w] to s\in S(w) . Hence, \widehat{Q} corresponds to a path Q in G from u to w that satisfies the requirements of the definition of \widehat{\mathrm{dist}}(u,w) and witnesses \widehat{\mathrm{dist}}(u,w)\leqslant|\widehat{Q}|-|V(G)| , as desired. This finishes the proof of the claim. ∎ Using the two previous claims, we infer that for every u\in U and w\in A_{R}(\mathcal{P}) it holds that \widehat{\mathrm{prof}}_{R,\mathcal{P}}[u](w)=\min(|R|+1,\pi[u](w)). (8) Indeed, \displaystyle\min\left(|R|+1,\pi[u](w)\right) \displaystyle=\min\left(|R|+1,\min\left\{\mathrm{dist}_{\widehat{G}}(u,s)~\colon~s\in S(w)\right\}+d_{w,t}-\mathrm{dist}_{\widehat{G}}(u,t)\right) \displaystyle=\min\big(|R|+1,\min\left\{\mathrm{dist}_{\widehat{G}}(u,s)~\colon~s\in S(w)\right\}-|V(G)| \displaystyle\qquad\qquad\qquad\qquad+\mathrm{dist}_{G}(w,R)-\mathrm{dist}_{G}(u,R)\big) by Claim 3.3 \displaystyle=\min\left(|R|+1,\widehat{\mathrm{dist}}(u,w)+\mathrm{dist}_{G}(w,R)-\mathrm{dist}_{G}(u,R)\right) by Claim 3.4 \displaystyle=\widehat{\mathrm{prof}}_{R,\mathcal{P}}[u](w). Here, in the third step we used the estimate \mathrm{dist}_{G}(u,R)-\mathrm{dist}_{G}(w,R)\leqslant|U|\leqslant|V(G)|-|R| , so if \min\left\{\mathrm{dist}_{\widehat{G}}(u,s)~\colon~s\in S(w)\right\}>2|V(G)| (which is equivalent to \widehat{\mathrm{dist}}(u,w)=\infty by Claim 3.4 ), then the minimum is attained at value |R|+1 . For every u\in U , we set B_{u}\coloneqq\left\{(w,i)\in A_{R}(\mathcal{P})\times\mathbb{Z}~|~i\leqslant\widehat{\mathrm{prof}}_{G,R}[u](w)\right\}. Claim 3.2 and ( 8 ) imply that the set system \{B_{u}~\colon~u\in U\} has size \mathcal{O}_{k}(|R|^{12}) . Now, for every v\in V(G) , we set S_{v}\coloneqq\left\{(s,i)\in R\times\{-|R|,\ldots,|R|\}~|~i\leqslant\mathrm{prof}_{R,s_{R}}[v](s)\right\}. The bound on the size of the set system \{B_{u}~\colon~u\in U\} and Lemma 3.3 imply that the size of \left\{S_{u}~\colon~u\in U\right\} is bounded by \mathcal{O}_{k}(|R|^{12}) . We conclude the proof of the lemma by bounding the size of \left\{S_{u}~\colon~u\in V(G)-U\right\} . For this, note that every vertex v\in V(G)-U is either a milestone for some path P\in\mathcal{P} or a vertex in the neutral prefix of a milestone. In the latter case, there is a path P\in\mathcal{P} and a milestone w\in M_{R}(P) such that S_{v}=S_{w} . Therefore, we have |\left\{S_{u}~\colon~u\in V(G)-U\right\}|\leqslant\sum_{P\in\mathcal{P}}|M_{R}(P)|\leqslant\mathcal{O}_{k}(|R|^{2}), where the second inequality follows from ( 5 ). Hence, the size of \left\{S_{v}~\colon~v\in V(G)\right\} is at most |\left\{S_{u}~\colon~u\in U\right\}|+|\left\{S_{u}~\colon~u\in V(G)-U\right\}|=\mathcal{O}_{k}(|R|^{12}). This finishes the proof of Theorem 1.4 . ∎ 4 Bounded Euler genus graphs with apices: proof of Theorem 1.5 In this section we prove Theorem 1.5 . (Note that Theorem 1.2 is a special case of Theorem 1.5 for k=1 .) We start by deriving the following corollary from Theorem 2.3 . Corollary 4.1 . Let V be a set of n points in \mathbb{R}^{d} . There is a data structure that uses \mathcal{O}\left(dn\log^{d-2}n\right) preprocessing time, \mathcal{O}\left(dn\log^{d-2}n\right) memory and answers the following queries in time \mathcal{O}\left(d\log^{d-2}n\right) : given r_{1},\dots,r_{d}\in\mathbb{R} , find \max_{v\in V}\min_{i\in[d]}(v_{i}+r_{i}) , where v_{i} denotes the i th coordinate of v . Proof. Fix query parameters r_{1},\dots,r_{d}\in\mathbb{R} . Let \lambda\coloneqq\max_{v\in V}\min_{i\in[d]}(v_{i}+r_{i}) denote the answer we want to find. We say that a pair (v,i)\in V\times[d] is good if for every j\in[d] , it holds that v_{j}-v_{i}\geqslant r_{i}-r_{j} . Let \lambda^{\prime}=\max\left\{v_{i}+r_{i}\colon i\in[d],v\in V,\textrm{ and }(v,i)\textrm{ is good}\right\}. We claim that \lambda=\lambda^{\prime}. (9) Let v^{\prime}=\text{argmax}_{v\in V}(\min_{i\in[d]}v_{i}+r_{i}) and let i^{\prime}=\text{argmin}_{i\in[d]}v^{\prime}_{i}+r_{i} . By the choice of i^{\prime} , for each j we have v^{\prime}_{j}+r_{j}\geqslant v^{\prime}_{i^{\prime}}+r_{i^{\prime}} , implying v^{\prime}_{j}-v^{\prime}_{i^{\prime}}\geqslant r_{i^{\prime}}-r_{j} . Hence (v^{\prime},i^{\prime}) is good, so \lambda^{\prime}\geqslant v^{\prime}_{i^{\prime}}+r_{i^{\prime}}=\lambda . On the other hand, consider a good pair (v^{\prime},i^{\prime}) maximizing v^{\prime}_{i^{\prime}}+r_{i^{\prime}} . The goodness of (v^{\prime},i^{\prime}) implies that i^{\prime}=\text{argmin}_{i\in[d]}v^{\prime}_{i}+r_{i} , hence \lambda\geqslant\min_{i\in[d]}v^{\prime}_{i}+r_{i}=v^{\prime}_{i^{\prime}}+r_{i^{\prime}}=\lambda^{\prime} . This proves ( 9 ). For every i\in[d] , we set V_{i} to be the set \{(v_{1}-v_{i},v_{2}-v_{i},\dots,v_{i-1}-v_{i},v_{i+1}-v_{i},\dots,v_{d}-v_{i}):v\in V\}\subseteq\mathbb{R}^{d-1}, and set w_{i}(v)\coloneqq v_{i} . Let \mathbb{D}_{i} be the data structure obtained by applying Theorem 2.3 to V_{i} and w_{i} . Consider the suffix range R_{i}\coloneqq\mathsf{Range}(r_{i}-r_{1},r_{i}-r_{2},\dots,r_{i}-r_{i-1},r_{i}-r_{i+1},\dots,r_{i}-r_{d})\subseteq\mathbb{R}^{d-1}. Now, by ( 9 ) we have that \lambda=\max\left\{r_{i}+\max\{w_{i}(v):v\in V_{i}\cap R_{i}\}\colon i\in[d]\right\}. This value can be computed by asking d queries to the data structures \mathbb{D}_{i} , for i\in[d] . This gives us a data structure satisfying the conditions given in the lemma statement. ∎ The main work in the proof of Theorem 1.5 will be done in the following lemma, which provides a fast computation of eccentricities once a suitable division is provided on input. We adopt the notation for divisions introduced in the statement of Theorem 2.4 . Lemma 4.2 . Fix constants 0<\alpha,\gamma,\rho<1 and k\in\mathbb{N} . Assume we are given a connected graph G on n vertices with O(n) edges with positive integer weights, a subset of vertices X , a subset of apices A\subseteq V(G) of size at most k , and a family \mathcal{R} with V(G)-A=\bigcup\mathcal{R} such that the following conditions are satisfied: • \sum_{R\in\mathcal{R}}|\partial R|\leqslant\mathcal{O}(n^{\gamma}) ; • for every R\in\mathcal{R} , |R|\leqslant\mathcal{O}(n^{\rho}) and G[R] is connected and contains O(|R|) edges; and • for every R\in\mathcal{R} , the number of distance profiles in G-A on \partial R is of \mathcal{O}(n^{\alpha}) . Then, we can compute X -eccentricity of every vertex of G in time \mathcal{O}(n^{\gamma+2\rho}\log n+(n^{1+\gamma}+n^{1+\alpha})\log^{k-1}n) . Proof. Let G^{\prime}\coloneqq G-A and X^{\prime}\coloneqq X\cap V(G^{\prime}) . Denote A\coloneqq\{a_{1},a_{2},\ldots,a_{k}\} . We first describe the procedure, and then discuss its time complexity. For every a\in A and u\in V(G) , we compute distance between a and u denoted d_{A}(a,u) . Step 1. We start by precomputing the following information for every region R\in\mathcal{R} . For all u,v\in R , we compute the distance between u and v in G^{\prime}[R] , denoted d_{R}(u,v) . For all s\in\partial R,u\in V(G^{\prime}) , we compute the distance between s and u in G^{\prime} , denoted d_{\partial R}(u,s) . We arbitrarily pick a pivot vertex s_{R}\in\partial R , and for brevity denote p_{R}[u]\coloneqq\mathrm{prof}_{\partial R,s_{R}}[u] , where the profile is considered in G^{\prime} . That is, p_{R}[u] is the (\partial R) -profile of u with respect to s_{R} : p_{R}[u](s)=d_{\partial R}(u,s)-d_{\partial R}(u,s_{R}),\quad\textrm{for all }u\in V(G^{\prime})\textrm{ and }s\in\partial R. We define P_{R}\coloneqq\{p_{R}[u]\colon u\in V(G^{\prime})\} . By our assumption, we have |P_{R}|\leqslant\mathcal{O}(n^{\alpha}) . Finally, for every profile p\in P_{R} , we list all vertices v\in X^{\prime}-R such that p_{R}[v]=p and set up the data structure of Corollary 4.1 for the points (d_{A}(a_{1},v),\dots,d_{A}(a_{k},v),d_{\partial R_{u}}(s_{R},v)) ; denote it by \mathbb{D}_{R,p} . Step 2. For every u\in V(G) , we compute \mathrm{ecc}_{X}(u) as follows. If u\in A , the answer is \max_{v\in X}d_{A}(u,v) . Hence, we may assume u\not\in A . Let R_{u} denote any region of \mathcal{R} containing u . For every v\in R_{u} , the shortest path from u to v in G either: • goes through an apex, in which case its length is \min_{a\in A}d_{A}(a,u)+d_{A}(a,v) ; or • is disjoint from A and intersects \partial R_{u} , in which case its length is \min_{s\in\partial R_{u}}d_{\partial R_{u}}(s,u)+d_{\partial R_{u}}(s,v) ; or • is contained entirely in R_{u} , in which case its length is d_{R_{u}}(u,v) . The length of this path is therefore the minimum among the three quantities. Using the above observation, we compute \mathrm{dist}_{G}(u,v) explicitly for each v\in R_{u} , and define \Delta^{R_{u}}_{u}\coloneqq\max_{v\in R_{u}\cap X}\mathrm{dist}_{G}(u,v) . For every v\in V(G)-(A\cup R_{u}) , the shortest path between u and v either crosses A or \partial R_{u} . The length of such path avoiding A is \min_{s\in\partial R_{u}}d_{\partial R_{u}}(s,u)+d_{\partial R_{u}}(s,v)=d_{\partial R_{u}}(s_{R},v)+\min_{s\in\partial R_{u}}\left(d_{\partial R_{u}}(s,u)+p_{R_{u}}[v](s)\right). We partition the vertices v by their profile p_{R_{u}}[v] and for every p\in P_{R_{u}} , we compute the maximum distance to a vertex with profile p separately. Let V_{p}=\{v\in X^{\prime}-R_{u}\mid p_{R_{u}}[v]=p\} . For every v\in V_{p} , we have \mathrm{dist}_{G}(u,v)=\min\left(\min_{a\in A}d_{A}(a,u)+d_{A}(a,v),d_{\partial R_{u}}(s_{R},v)+\min_{s\in\partial R_{u}}\left(d_{\partial R_{u}}(s,u)+p(s)\right)\right). We set r_{i}\coloneqq d_{A}(a,u) for i\in[k] , and r_{k+1}\coloneqq\min_{s\in\partial R_{u}}\left(d_{\partial R_{u}}(s,u)+p(s)\right) . Now, \max_{v\in V_{p}}\mathrm{dist}_{G}(u,v)=\max_{v\in V_{p}}\min(r_{1}+d_{A}(a_{1},v),\dots,r_{k}+d_{A}(a_{k},v),r_{k+1}+d_{\partial R_{u}}(s_{R},v)). This value can be computed by querying r_{1},\dots,r_{k+1} to the data structure \mathbb{D}_{R_{u},p} . We define \Delta^{V(G)-(A\cup R_{u})}_{u} as the maximum of such values over all p\in P_{R_{u}} . Finally, we set \Delta^{A}_{u}\coloneqq\max_{a\in A\cap X}d_{A}(a,u) , and report \mathrm{ecc}_{X}(u)=\max\left(\Delta^{A}_{u},\Delta^{R_{u}}_{u},\Delta^{V(G)-(A\cup R_{u})}_{u}\right) . It remains to argue that this algorithm can be implemented in the desired running time. For any source u\in V(G) , distance from u to all vertices of G can be calculated in time \mathcal{O}((|V(G)|+|E(G)|)\log|V(G)|) using Dijkstra’s algorithm. Therefore: • computing d_{A}(a,\cdot) for all a can be done in time \mathcal{O}(n\log n) , • computing d_{\partial R}(\cdot,\cdot) for all R can be done in time \mathcal{O}(n\log n\cdot\sum_{R\in\mathcal{R}}|\partial R|)\leqslant\mathcal{O}(n^{1+\gamma}\log n) , • computing d_{R}(\cdot,\cdot) for all R\in\mathcal{R} can be done in time \mathcal{O}(|\mathcal{R}|n^{2\rho}\log n)\leqslant\mathcal{O}(n^{\gamma+2\rho}\log n) ; constructing G[R] takes \mathcal{O}(|R|^{2}\log n)=\mathcal{O}(n^{2\rho}\log n) time and calculating all pairs shortest paths can be done in time \mathcal{O}(|R||E(G[R])|\log n)=\mathcal{O}(n^{2\rho}\log n) . Finally, the total size of the data structures \mathbb{D}_{R,p} over all R,p is \mathcal{O}(|\mathcal{R}|n)=\mathcal{O}(n^{1+\gamma}) , hence we can construct them in time \mathcal{O}(n^{1+\gamma}\log^{k-1}n) . Consider u\in V(G)-A fixed in step 2. Computing \Delta^{R_{u}}_{u} takes \mathcal{O}(|R|\cdot|\partial R_{u}|) time. Computing \Delta^{A}_{u} can be done in constant time. Computing \Delta^{V(G)-(A\cup R_{u})}_{u} requires asking |P_{R_{u}}| queries to some \mathbb{D}_{R,p} , which takes \mathcal{O}(n^{\alpha}\log^{k-1}n) time in total. In total, step 2 for all vertices u can be done in time \mathcal{O}(n^{1+\alpha}\log^{k-1}n+n^{\rho}\cdot\sum_{u\in V(G)-A}|\partial R_{u}|)=\mathcal{O}(n^{1+\alpha}\log^{k-1}n+n^{\gamma+2\rho}) . We conclude that the total running time is \mathcal{O}(n^{\gamma+2\rho}\log n+(n^{1+\gamma}+n^{1+\alpha})\log^{k-1}n) . ∎ The next statement is a reformulation of Theorem 1.5 . Theorem 4.3 . Fix constants k,g\in\mathbb{N} . Let \mathcal{C} denote the class of all graphs that can be obtained by taking a graph G of Euler genus bounded by g , and adding k apices adjacent arbitrarily to the rest of G and to each other. Then there is an algorithm that given an unweighted graph G belonging to \mathcal{C} , together with its set of apices A , computes the eccentricity of every vertex in time \mathcal{O}_{k,g}\left(n^{1+\frac{24}{25}}\log^{k-1}n\right) . Proof. Let A=\{a_{1},\dots,a_{k}\} denote the set of apices and let G^{\prime}=G-A . Fix \rho\coloneqq\frac{2}{25} . Since graphs of bounded genus exclude some fixed clique as a minor, by Theorem 2.4 (with \varepsilon=\rho/2 ) we can find an \mathcal{O}(n^{\rho}) -division \mathcal{R} of G^{\prime} satisfying \sum_{R\in\mathcal{R}}|\partial R|=\mathcal{O}(n^{1-\frac{\rho}{2}}) in time \mathcal{O}(n^{1+\rho}) . By Theorem 1.4 , the graph G^{\prime} has a degree 12 polynomial bound on the number of distance profiles. In particular, the number of profiles on every \partial R is of \mathcal{O}(|R|^{12})=\mathcal{O}(n^{12\rho}) . Let X\coloneqq V(G) , \gamma\coloneqq 1-\frac{\rho}{2}=\frac{24}{25} and \alpha\coloneqq 12\rho=\frac{24}{25} . Now, applying Lemma 4.2 gives us an algorithm computing all eccentricities in time \mathcal{O}(n^{1+\frac{24}{25}}\log^{k-1}n) . ∎ 5 The general case: Proof of Theorem 1.6 First, we show that data structure of Corollary 4.1 can be used to compute distances witnessed by shortest paths that pass through a constant-size separator. Lemma 5.1 . Fix a constant k\in\mathbb{N} . There exists an algorithm which as the input receives an edge-weighted graph G on n vertices and m edges together with a partition of its vertices into three sets A,B,C such that |B|\leqslant k and there are no edges between A and C , and as the output computes \max_{c\in C}\mathrm{dist}(a,c) for every a\in A . The running time is \mathcal{O}(m\log n+n\log^{k-1}n) . Proof. Let B=\{b_{1},\ldots,b_{k}\} . For any a\in A,c\in C , we have \mathrm{dist}(a,c)=\min_{i\in[k]}\mathrm{dist}(a,b_{i})+\mathrm{dist}(c,b_{i}) . First, we run Dijkstra’s algorithm from every vertex in B to find \mathrm{dist}(v,b_{i}) for every v\in V(G) and i\in[k] . Next, we use Corollary 4.1 to construct a data structure \mathbb{D} for the point set \{(\mathrm{dist}(c,b_{1}),\dots,\mathrm{dist}(c,b_{k}))\colon c\in C\}\subseteq\mathbb{R}^{k} . Now, the value \max_{c\in C}\mathrm{dist}(a,c) for any given a is equal to the answer of \mathbb{D} to the query with argument (\mathrm{dist}(a,b_{1}),\dots,\mathrm{dist}(a,b_{k})) . ∎ After computing the distances over a constant-size separator, we will use the following observation to simplify one of the sides of the separation. Lemma 5.2 . Let G be a edge-weighted connected graph and let A,B,C be a partition of its vertices such that there are no edges between A and C . For every pair of vertices u,v\in B , let P_{u,v} be any shortest path from u to v with all internal vertices in C (assuming such a path exists). Let G^{\prime} denote a graph obtained from G[A\cup B] by adding an edge from u to v of weight equal to the length of P_{u,v} , for all u,v\in B for which P_{u,v} exists. Then, \mathrm{dist}_{G}(s,t)=\mathrm{dist}_{G^{\prime}}(s,t)\qquad\textrm{for all }s,t\in A\cup B. Proof. Let G^{\prime\prime} be the graph obtained by adding new edges of G^{\prime} to G . Fix any s,t\in A\cup B and let P denote the shortest path from s to t in G^{\prime\prime} which minimizes the number of vertices from C visited. Naturally, the weight of P is equal \mathrm{dist}_{G}(s,t) . Assume that such path visits at least one vertex of C . Then, the path P is of the form s\xrightarrow{P_{1}}x\xrightarrow{P_{2}}y\xrightarrow{P_{3}}t , where x,y\in B and all the internal vertices of P_{2} are in C . By the construction of G^{\prime} , P_{2} can be replaced with a direct edge from x to y of the same weight. We obtain a same weight path with a smaller number of vertices of C visited, which is a contradiction. Therefore, P is entirely contained in A\cup B , hence it exists in G^{\prime} . This shows that \mathrm{dist}_{G}(s,t)=\mathrm{dist}_{G^{\prime}}(s,t) . ∎ The next lemma encapsulates the main algorithmic content of the proof of Theorem 1.6 . The algorithm will split the tree decomposition provided on input into smaller parts for which the eccentricities are easier to calculate. We use the following lemma to handle a single such part. Lemma 5.3 . Fix constants k,g\in\mathbb{N},0<\delta<\frac{1}{54} . Assume we are given n\in\mathbb{N} , an edge-weighted graph G on at most n vertices with a weight function w\colon E(G)\to\mathbb{N} , a vertex subset A and a collection of non-empty vertex subsets V_{0},V_{1},\dots,V_{\ell} satisfying the following conditions: • The sum of weights of all the edges in G is bounded by \mathcal{O}(n) . • V(G)-A=V_{0}\cup V_{1}\cup\dots\cup V_{\ell} . • |A|\leqslant k . • For every i\in[\ell] , G[V_{i}-V_{0}] is connected, N_{G}(V_{i}-V_{0})=V_{i}\cap V_{0} , |V_{i}|=\mathcal{O}(n^{\delta}) , and |V_{0}\cap V_{i}|\leqslant 4 . • For all i,j\in[\ell],i\neq j , V_{i}-V_{0} and V_{j}-V_{0} are disjoint and non-adjacent in G . • Every edge uv\in E(G) with u,v\not\in A is contained in G[V_{i}] for some i\in\{0,1,\ldots,\ell\} . • The graph obtained by taking G[V_{0}] and adding a clique on V_{0}\cap V_{i} for every i\in[\ell] has Euler genus bounded by g . Then, we can compute the eccentricity of every vertex of G in time \mathcal{O}\left(n^{1+\frac{150+54\delta}{151}}\log^{k}n\right) . Proof. Fix \delta^{\prime}=\frac{1+97\delta}{151} ; we have \delta^{\prime}-\delta=\frac{1-54\delta}{151}>0 . Let E_{i} denote the set of edges with one endpoint in V_{i} and the other endpoint in V_{i}-V_{0} . For i\in[\ell] , we shall say that V_{i} is heavy if the sum of weights of E_{i} is larger than n^{\delta^{\prime}} . Since the sets E_{i} are pairwise disjoint and the total sum of weights of all the edges is bounded by \mathcal{O}(n) , the number of heavy subsets is bounded by \mathcal{O}(n^{1-\delta^{\prime}}) . Without loss of generality, we may assume that V_{\ell^{\prime}+1},\dots,V_{\ell} are heavy and V_{1},\dots,V_{\ell^{\prime}} are not, for some \ell^{\prime}\in\{0,\ldots,\ell\} . For any source vertex s , we can calculate distances from s to every vertex of G using breadth first search in time \mathcal{O}(\sum_{e\in E(G)}w(e))=\mathcal{O}(n) . In particular, for every \ell^{\prime}0 . The graph G^{*}_{0} is a unit-weight graph and is K_{t} -minor-free. Hence, by applying Theorem 2.4 to G^{*}_{0} (with \varepsilon=\rho^{\prime}/2 ) we obtain an n^{\rho^{\prime}} -division \mathcal{R}_{0} in time \mathcal{O}(n^{1+\rho^{\prime}}) . We extend it to G^{\prime}-A by mapping every contracted vertex v^{*}_{i} to N_{G^{\prime}-A}[V^{\prime}_{i}-V^{\prime}_{0}]=(V^{\prime}_{i}-V^{\prime}_{0})\cup(V_{0}\cap V_{i}) . Formally, we put V^{\prime\prime}_{i}\coloneqq N_{G^{\prime}-A}[V^{\prime}_{i}-V^{\prime}_{0}] and \mathcal{R}\coloneqq\left\{(R_{0}\cap V^{\prime}_{0})\cup\bigcup_{i\colon v^{*}_{i}\in R_{0}}V^{\prime\prime}_{i}\colon R_{0}\in\mathcal{R}_{0}\right\}. Now, we argue that \mathcal{R} is a reasonable division of G^{\prime}-A . Clearly, all sets R\in\mathcal{R} are connected in G^{\prime}-A . Pick any R\in\mathcal{R} and let R_{0} be its corresponding set in \mathcal{R}_{0} . Every vertex v^{*}_{i} is mapped to a set of size \mathcal{O}(n^{\delta^{\prime}}) , therefore |R|\leqslant|R_{0}|\cdot\mathcal{O}(n^{\delta^{\prime}})=\mathcal{O}(n^{\rho^{\prime}+\delta^{\prime}}). By our construction, for every i\in[\ell^{\prime}] , R is either disjoint from V^{\prime}_{i}-V^{\prime}_{0} or contains whole N_{G^{\prime}-A}[V^{\prime}_{i}-V^{\prime}_{0}] . This means that no vertex belonging to any V^{\prime}_{i}-V^{\prime}_{0} can be in \partial R , hence \partial R\subseteq V^{\prime}_{0} . Pick any u\in\partial R\cap R_{0} . Assume that u\not\in\partial R_{0} . Then every vertex of N_{G_{0}^{*}}(u) must be in R_{0} , hence N_{G-A^{\prime}}(u)\subseteq R , which is a contradiction. This means that \partial R\cap R_{0}\subseteq\partial R_{0} . Pick any u\in\partial R-R_{0} . Then, u\in V_{0}\cap V_{i} for some i\in[\ell^{\prime}] such that v_{i}^{*}\in R_{0} . Moreover, v_{i}^{*}\in\partial R_{0} and is adjacent to u in G_{0}^{*} . The number of such u is bounded by 4|\partial R_{0}\cap\{v_{1}^{*},\dots,v_{\ell^{\prime}}^{*}\}| . Putting two cases together, we obtain: \sum_{R\in\mathcal{R}}|\partial R|=\sum_{R\in\mathcal{R}}\left(|\partial R\cap R_{0}|+|\partial R-R_{0}|\right)\leqslant\sum_{R_{0}\in\mathcal{R}_{0}}\left(|\partial R_{0}|+4|\partial R_{0}\cap\{v_{1}^{*},\dots,v_{\ell^{\prime}}^{*}\}|\right)=\mathcal{O}(n^{1-\frac{1}{2}\rho^{\prime}}). It remains to show the following claim. Claim 5.3 . Pick any R\in\mathcal{R},s_{R}\in R . The number of different distance profiles on R relative to s_{R} in G^{\prime}-A is of \mathcal{O}(n^{48\rho^{\prime}+54\delta^{\prime}}) . Proof. We look at every vertex v\in V(G^{\prime})-A and consider three cases: v\in R , v\in V^{\prime}_{0} , and v\in V^{\prime}_{i}-(V^{\prime}_{0}\cup R) for some i\in[\ell^{\prime}] . By our construction, R\cap V^{\prime}_{0} is non-empty, hence w.l.o.g. we can assume that s_{R}\in V^{\prime}_{0} as whether two vertices have the same profile on R is independent of the choice of the pivot vertex. In the first case, there are at most |R|=\mathcal{O}(n^{\rho^{\prime}+\delta^{\prime}}) such vertices, hence they realise at most that many profiles. In the second case, we want to observe that profile of any vertex v\in V^{\prime}_{0} on R depends only on its profile on R\cap V^{\prime}_{0} (relative to s_{R} ). Pick any t\in R-V^{\prime}_{0} . Then t\in V^{\prime}_{i}-V^{\prime}_{0} for some i\in[\ell^{\prime}] , V_{i}\cap V_{0}\subseteq R\cap V^{\prime}_{0} , and every path from v to t intersects V_{i}\cap V_{0} . In particular, distances from v to vertices of V_{i}\cap V_{0} determine its distance to t , which proves the observation. Let \tilde{G}_{0} denote the graph obtained by taking G^{\prime}[V^{\prime}_{0}] and for every i\in[\ell^{\prime}],u,v\in V_{0}\cap V_{i} adding a disjoint path from u to v of length \mathrm{dist}(u,v) . Let P_{i} denote the vertex set of paths added between V_{0}\cap V_{i} . For every t\in V^{\prime}_{0} we have \mathrm{dist}_{G^{\prime}-A}(v,t)=\mathrm{dist}_{\tilde{G}_{0}}(v,t) , so it suffices to bound the number of profiles on R\cap V^{\prime}_{0} in \tilde{G}_{0} . By our assumptions, \tilde{G}_{0} has Euler genus bounded by g and all P_{i} are of size \mathcal{O}(n^{\delta^{\prime}}) . Let R_{0} be the set of \mathcal{R}_{0} corresponding to R . Let \tilde{R}_{0} denote the set (R\cap V^{\prime}_{0})\cup\bigcup_{i:v^{*}_{i}\in R_{0}}P_{i} . Such set is connected in \tilde{G}_{0} . Moreover, similarly to R , its size is \mathcal{O}(n^{\rho^{\prime}+\delta^{\prime}}) . Applying Theorem 1.4 , we get that the number of distance profiles on \tilde{R}_{0} in \tilde{G}_{0} is \mathcal{O}(n^{12(\rho^{\prime}+\delta^{\prime})}) , which also bounds the number of profiles on R in G^{\prime}-A realised by V^{\prime}_{0} . For the third case, assume v\in V^{\prime}_{i}-(V^{\prime}_{0}\cup R) for some i\in[\ell^{\prime}] . Every path from v to any vertex of R in G^{\prime}-A intersects V_{i}\cap V_{0} . Let v_{1},\dots v_{p} be the vertices of V_{i}\cap V_{0} , where p\leqslant 4 . The profile of v on R is then determined by the following: (a) the profile of each v_{j} on R , (b) \mathrm{dist}_{G^{\prime}-A}(v,v_{j})-\mathrm{dist}_{G^{\prime}-A}(v,v_{1}) for each 2\leqslant j\leqslant p , and (c) \mathrm{dist}_{G^{\prime}-A}(s_{R},v_{j})-\mathrm{dist}_{G^{\prime}-A}(s_{R},v_{1}) for each 2\leqslant j\leqslant p where s_{R} is some pivot vertex of R . By the previous case, the number of distance profiles of each v_{j} is \mathcal{O}(n^{12(\rho^{\prime}+\delta^{\prime})}) . The distances between v and v_{j} are bounded by |V^{\prime}_{i}| , hence each quantity described in (b) can take \mathcal{O}(n^{\delta^{\prime}}) different possible values. Similarly, since v_{1} and v_{j} are connected via V^{\prime}_{i} , |\mathrm{dist}_{G^{\prime}-A}(s_{R},v_{j})-\mathrm{dist}_{G^{\prime}-A}(s_{R},v_{1})|\leqslant\mathcal{O}(n^{\delta^{\prime}}) . The number of different possible profiles of such v is therefore bounded by \mathcal{O}(n^{48(\rho^{\prime}+\delta^{\prime})+6\delta^{\prime}})=\mathcal{O}(n^{48\rho^{\prime}+54\delta^{\prime}}) . This finishes the proof of the claim. ∎ Now we can apply Lemma 4.2 to graph G^{\prime} with apex set A , X=V(\widetilde{G}) , and the following constants: \rho=\rho^{\prime}+\delta^{\prime},\qquad\gamma=1-\frac{1}{2}\rho^{\prime},\quad\textrm{and}\quad\alpha=48\rho^{\prime}+54\delta^{\prime}. This allows us to calculate all V(\widetilde{G}) -eccentricities in G^{\prime} in time \mathcal{O}\left(\left(n^{2-\frac{1}{2}\rho^{\prime}}+n^{1+48\rho^{\prime}+54\delta^{\prime}}\right)\log^{k}n\right)=\mathcal{O}\left(n^{1+\frac{150+54\delta}{151}}\log^{k}n\right). Since for each v\in V(\widetilde{G}) we have \mathrm{ecc}_{\widetilde{G}}(v)=\max_{u\in V(\widetilde{G})}\mathrm{dist}_{\widetilde{G}}(v,u)=\max_{u\in V(\widetilde{G})}\mathrm{dist}_{G^{\prime}}(v,u) , this means that we have successfully computed all the eccentricities in \widetilde{G} ; and as we argued, this is enough to compute all the eccentricities in G as well. Finally, the total running time of the algorithm is \mathcal{O}\left(n^{1+\frac{150+54\delta}{151}}\log^{k}n+n^{2-\delta^{\prime}+\delta}\right)=\mathcal{O}\left(n^{1+\frac{150+54\delta}{151}}\log^{k}n\right). ∎ Lemma 5.4 . Fix constants k,g\in\mathbb{N},0<\delta<\frac{1}{54} . Assume we are given n\in\mathbb{N} , an edge-weighted graph G on at most n vertices with a weight function w\colon E(G)\to\mathbb{N} , a vertex subset A and a collection of non-empty vertex subsets V_{0},V_{1},\dots,V_{\ell} satisfying the same conditions as in Lemma 5.3 with the following differences: • we don’t require G[V_{i}-V_{0}] to be connected and V_{i}-V_{0} to be adjacent to whole V_{i}\cap V_{0} ; • instead of |V_{0}\cap V_{i}|\leqslant 4 , we require |V_{0}\cap V_{i}|\leqslant k . Then, we can compute the eccentricity of every vertex of G in time \mathcal{O}\left(n^{1+\frac{150+54\delta}{151}}\log^{k+5g}n\right) . Proof. We will reduce our input to one which will satisfy the conditions of Lemma 5.3 . We start by addressing the adhesions V_{0}\cap V_{i} containing too many vertices. Let G_{0} denote the graph G[V_{0}] with cliques placed at V_{0}\cap V_{i} for every i\in[\ell] . For every i\in[\ell] we repeat the following procedure: while |V_{0}\cap V_{i}|>4 , remove arbitrary 5 vertices from V_{0}\cap V_{i} . Since |V_{0}\cap V_{i}|\leqslant k for each i\in[\ell] , this procedure can be implemented in total time \mathcal{O}(n) . As a result, at the end we have |V_{0}\cap V_{i}|\leqslant 4 for all i\in[\ell] . Let M be the set of all the removed vertices. By our assumptions, G_{0} has Euler genus bounded by g , hence it cannot contain g+1 pairwise disjoint copies of K_{5} (as the Euler genus of a graph is the sum of the Euler genera of its 2-connected components [ 17 ] and K_{5} is not planar). Each removed quintiple of vertices induces a K_{5} in G_{0} , hence we have |M|\leqslant 5g . We set A^{\prime}=A\cup M and may thus assume that V_{i} is disjoint from A^{\prime} for all 0\leqslant i\leqslant\ell . Now, fix i\in[\ell] . Let C^{i}_{1},\dots,C^{i}_{r_{i}} denote the connected components of V_{i}-V_{0} in G-A^{\prime} . We define W^{i}_{j}:=N_{G-A^{\prime}}[C^{i}_{j}] for every j\in[r_{i}] . Clearly, all W^{i}_{j} induce a connected subgraph of G and satisfy N_{G-A^{\prime}}(W^{i}_{j}-V_{0})=W^{i}_{j}\cap V_{0} . We put V^{\prime}_{0}:=V_{0} and enumerate \{V^{\prime}_{1},V^{\prime}_{2},\dots V^{\prime}_{\ell^{\prime}}\}:=\{W^{i}_{j}\colon i\in[\ell],j\in[r_{i}]\}. It is easy to verify that the sets A^{\prime} and V^{\prime}_{0},V^{\prime}_{1},\dots,V^{\prime}_{\ell^{\prime}} satisfy the conditions of Lemma 5.3 . We apply said lemma to calculate the eccentricity of every vertex of G in the desired time. ∎ The next statement is a reformulation of Theorem 1.6 . Theorem 5.5 . Fix constants k,g\in\mathbb{N} . Assume we are given a graph G on n vertices together with its tree decomposition (T,\beta) and a set of private apices A_{t}\subseteq\beta(t) for each node t\in V(T) such that the following conditions hold: • For every node t\in V(T) , we have |A_{t}|\leqslant k . • For every edge st\in E(T) , we have |\beta(v)\cap\beta(u)|\leqslant k . • For every node t\in V(T) , graph obtained by taking G[\beta(t)]-A_{t} and turning (\beta(t)\cap\beta(s))-A_{t} into a clique for every edge st\in E(T) has Euler genus bounded by g . Then, we can compute the eccentricity of every vertex of G in time \mathcal{O}\left(n^{1+\frac{355}{356}}\log^{k+5g}n\right) . Proof. We may assume that |V(T)|\leqslant n , for every tree decomposition with no two bags comparable by inclusion has this property; and adjacent comparable bags can be merged by contracting the edge between them. For a node t\in V(T) , by the weight of t we mean the size of the corresponding bag, that is, |\beta(t)| . For any subset of nodes S\subseteq V(T) , we define \beta(S)\coloneqq\bigcup_{t\in S}\beta(t) By the weight of S , we mean the total weight of the elements of S , that is, \sum_{t\in S}|\beta(t)| . Claim 5.4 . The weight of V(T) is of \mathcal{O}(n) . Proof. The sets \beta^{\prime}(t):=\beta(t)-\bigcup_{s\in N_{T}(t)}\beta(s) are pairwise disjoint. We have \sum_{t\in V(T)}|\beta(t)|=\sum_{t\in V(T)}|\beta^{\prime}(t)|+2\cdot\sum_{st\in E(T)}|\beta(s)\cap\beta(t)|\leqslant|V(T)|+2k|E(T)|=\mathcal{O}(n). ∎ Since every bag induces a graph of bounded Euler genus, the number of edges contained in a bag is linear in its size. In particular, this implies that the total number of edges of G is also bounded by \mathcal{O}(n) . We set \delta\coloneqq\frac{1}{356}\qquad\textrm{and}\qquad\Delta\coloneqq\frac{355}{356}. Root the tree T in an arbitrarily chosen node; this naturally imposes an ancestor-descendant relation in T (for convenience, every node is considered its own ancestor and descendant). We start by partitioning T into connected subtrees using the following procedure. We proceed bottom-up over T , processing nodes in any order so that a node is processed after all its strict descendants have been processed. Along the way, we mark some nodes and split the edges of T into heavy and light. Let t\in V(T) be the currently processed non-root node of T and let e\in E(T) be the edge connecting t with its parent. If the total weight of all the unmarked nodes that are descendants of t is at least n^{\delta} (recall that this includes t itself as well), then we declare e heavy and mark all the descendants of t that were unmarked so far. Otherwise, the edge e is declared light and the procedure proceeds to further nodes of T . Observe that removing all heavy edges splits T into connected subtrees, say T^{\prime}_{1},\cdots T^{\prime}_{m} . All of the subtrees, except for possibly the subtree containing the root node, are of weight at least n^{\delta} . In particular, the number of subtrees m , and therefore the number of heavy edges, is bounded by \mathcal{O}(n^{1-\delta}) . Moreover, in every subtree T^{\prime}_{i} , removing the node closest to the root splits T^{\prime}_{i} into smaller components, each of weight less than n^{\delta} . Fix a heavy edge e and let T^{e}_{1} and T^{e}_{2} be the two subtrees into which T splits after removing e . Let X^{e}_{i}=\beta(T^{e}_{i}) for i\in\{1,2\} . Put A_{e}=X^{e}_{1}-X^{e}_{2} , C_{e}=X^{e}_{2}-X^{e}_{1} , and B_{e}=X^{e}_{1}\cap X^{e}_{2} . By the properties of tree decompositions, such choice of A_{e},B_{e},C_{e} satisfies the conditions of Lemma 5.1 , hence in time \mathcal{O}(n\log^{k-1}n) we can compute \max_{v\in X^{e}_{2}}\mathrm{dist}_{G}(u,v) for every u\in X^{e}_{1} , and \max_{u\in X^{e}_{1}}\mathrm{dist}_{G}(u,v) for every v\in X^{e}_{2} . Computing this for every heavy edge e takes total time \mathcal{O}(n^{2-\delta}\log^{k-1}n) . Fix any subtree T^{\prime}=T^{\prime}_{j} . Let e_{1}=t^{e_{1}}_{1}t^{e_{1}}_{2},e_{2}=t^{e_{2}}_{1}t^{e_{2}}_{2},\dots,e_{\ell}=t^{e_{\ell}}_{1}t^{e_{\ell}}_{2} denote the heavy edges incident to T^{\prime} , where t^{e_{i}}_{1}\in V(T^{\prime}) and V(T^{\prime})\subseteq V(T_{1}^{e_{i}}) for every i\in[\ell] . For a vertex v\in\beta(T^{\prime}) , let d_{0}(v)=\max_{u\in\beta(T^{\prime})}\mathrm{dist}_{G}(v,u)\qquad\textrm{and}\qquad d_{i}(v)=\max_{u\in X_{2}^{e_{i}}}\mathrm{dist}_{G}(v,u),\quad\textrm{for }i\in[\ell]. We have \mathrm{ecc}(v)=\max\{d_{i}(v)\colon i\in\{0,1,\ldots,\ell\}\} .The values of d_{i}(v) are already calculated for all i\in[\ell] , hence it remains to compute d_{0}(v) . For every i\in[\ell] and every pair of vertices u,v\in\beta(t^{e_{i}}_{1})\cap\beta(t^{e_{i}}_{2}) we find a shortest path between u and v with all internal vertices inside X^{e_{i}}_{2} (or determine that it doesn’t exist). For a fixed u,v this can be done in time \mathcal{O}(n) . Since in total we perform this step at most 2k^{2} times per heavy edge, it takes \mathcal{O}(n^{2-\delta}) time in total. Let P_{i,u,v} denote such path, assuming it exists. Let G^{\prime} denote the graph obtained from G[\beta(T^{\prime})] by taking every i,u,v for which P_{i,u,v} exists and adding an edge between u and v of weight equal to the total weight of P_{i,u,v} . The weight of every edge inserted in \beta(t^{e_{i}}_{1})\cap\beta(t^{e_{i}}_{2}) is bounded by |X^{e_{i}}_{2}|+1 . The total weight of all edges inserted is therefore at most \sum_{i\in[\ell]}|\beta(t^{e_{i}}_{1})\cap\beta(t^{e_{i}}_{2})|^{2}\cdot(|X^{e_{i}}_{2}|+1)\leqslant k^{2}\sum_{i\in[\ell]}(|X^{e_{i}}_{2}|+1)=\mathcal{O}(n), where the last equality follows from the fact that all the trees T^{e_{i}}_{2} are pairwise disjoint. By Lemma 5.2 , we have \mathrm{dist}_{G^{\prime}}(u,v)=\mathrm{dist}_{G}(u,v) for each u,v\in\beta(T^{\prime}) . Hence, computing d_{0}(v) for every v\in\beta(T^{\prime}) is equivalent to computing the eccentricity of every vertex in G^{\prime} . If the size of \beta(T^{\prime}) is smaller than n^{\Delta} , we compute the eccentricities naively in time \mathcal{O}(|\beta(T^{\prime})|^{2}) , noting that G^{\prime} has \mathcal{O}(|\beta(T^{\prime})|) edges (thanks to Claim 5.4 and bounded genus assumption of the last bullet of the theorem statement). Otherwise, we argue that we can use the algorithm in Lemma 5.3 as follows. Let t be the node of T^{\prime} closest to the root. Let s_{1},\dots,s_{p} be the children of t in T and let T^{\prime\prime}_{i} denote the connected component of T^{\prime}-\{t\} containing s_{i} . Set V_{0}=\beta(t) and V_{i}=\beta(T^{\prime\prime}_{i}) for i\in[p] . It is now easy to verify that G^{\prime} and sets A,\{V_{i}\colon 0\leqslant i\leqslant p\} selected this way satisfy the assumptions of Lemma 5.4 . This allows us to use it to compute the eccentricities in G^{\prime} in time \mathcal{O}\left(n^{1+\frac{150+54\delta}{151}}\log^{k+5g}n\right)=\mathcal{O}\left(n^{1+\frac{354}{356}}\log^{k+5g}n\right). As we argued, from these eccentricities, we may easily compute all the eccentricities in G . Now, let us analyse the total running time of the whole algorithm. We invoke Lemma 5.3 \mathcal{O}(n^{1-\Delta}) times, since we apply it only to subtrees T^{\prime}_{i} of size at least n^{\Delta} . The total running time of those applications is hence \mathcal{O}\left(n^{2+\frac{354}{356}-\Delta}\log^{k+5g}n\right)=\mathcal{O}\left(n^{1+\frac{355}{356}}\log^{k+5g}n\right). We compute the eccentricities naively for subtrees smaller than n^{\Delta} , hence the total running time of this computation is \sum_{i\in[m]\colon|\beta(T^{\prime}_{i})|\leqslant n^{\Delta}}|\beta(T^{\prime}_{i})|^{2}\leqslant n^{\Delta}\cdot\sum_{i\in m}|\beta(T^{\prime}_{i})|=\mathcal{O}(n^{1+\Delta})=\mathcal{O}\left(n^{1+\frac{355}{356}}\right). The rest of computation can be done in \mathcal{O}(n^{2-\delta}\log^{k}n) . Therefore, the whole algorithm runs in time \mathcal{O}\left(n^{1+\frac{355}{356}}\log^{k+5g}n\right) . ∎