Abstract 1 Introduction 2 Preliminaries 3 Distance profiles in graphs of bounded Euler genus 4 Bounded Euler genus graphs with apices: proof of Theorem 5 References

Faster Diameter Computation in Graphs of Bounded Euler Genus

Kacper Kluk ORCID Institute of Informatics, University of Warsaw, Poland Marcin Pilipczuk ORCID Institute of Informatics, University of Warsaw, Poland Michał Pilipczuk ORCID Institute of Informatics, University of Warsaw, Poland Giannos Stamoulis ORCID Université Paris Cité, CNRS, IRIF, F-75013, Paris, France
Abstract

We show that for any fixed integer k0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time

𝒪k(n2125).

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 after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound

𝒪k(n21356log6kn).

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 Kh-minor-free graphs, but the running time bound is 𝒪h(n2ch) for some constant ch>0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter 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.

Keywords and phrases:
Diameter, eccentricity, subquadratic algorithms, surface-embeddable graphs
Category:
Track A: Algorithms, Complexity and Games
Copyright and License:
[Uncaptioned image] © Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, and Giannos Stamoulis; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Mathematics of computing Graph algorithms
; Mathematics of computing Graphs and surfaces ; Mathematics of computing Paths and connectivity problems ; Theory of computation Fixed parameter tractability ; Theory of computation Shortest paths
Related Version:
Full Version: https://arxiv.org/abs/2502.07501 [9]
Acknowledgements:
Marcin thanks Jacob Holm, Eva Rotenberg, and Erik Jan van Leeuwen for many discussions on subquadratic algorithms for diameter while his stay on sabbatical in Copenhagen.
Funding:
margin: [Uncaptioned image] 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.
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Computing the diameter of an input (undirected, unweighted) graph G is a classic computational problem that can be trivially solved in 𝒪(nm) time111We 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 𝒪(m2ε), for any fixed ε>0, would break the Strong Exponential Time Hypothesis [16]. 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 𝒪~(n11/6) time; this complexity has been later improved by Gawrychowski, Kaplan, Mozes, Sharir, and Weimann to 𝒪~(n5/3) [8]222The 𝒪~() notation hides factors polylogarithmic in n, and the 𝒪k() notation hides factors depending on a parameter k.. A subsequent line of research [5, 6, 12] generalized this result to Kh-minor-free graphs: for every integer h, there exists a constant ch>0 such that the diameter problem in n-vertex Kh-minor-free graphs can be solved in time 𝒪h(n2ch). In the works [6, 12], it holds that ch=Ω(1h); so the savings tend to zero as the size of the excluded clique minor increases.

However, known lower bounds, including the one of [16], does not exclude the possibility that ch can be made a universal constant. That is, no known lower bound refutes the following conjecture:

Conjecture 1.

There exists a constant c>0 such that, for every integer h>1, the diameter problem in (unweighted, undirected) n-vertex Kh-minor-free graphs can be solved in time 𝒪h(n2c).

Graphs of bounded Euler genus.

Our main result is the verification of Conjecture 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 vV(G) is defined as ecc(v)maxuV(G)distG(u,v), where distG(,) is the distance metric in G.

Theorem 2.

For every integers k1, there exists an algorithm that, given an (unweighted, undirected) n-vertex graph G of Euler genus at most k, runs in time 𝒪k(n2125) 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 2 the main ingredient is an improved combinatorial bound on the number of so-called distance profiles [12] 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 to some extent.

To explain our bound on distance profiles, we need to recall several relevant definitions.

Let G be a graph, RV(G) be a subset of vertices, and sRR be a vertex in R. The distance profile of a vertex uV(G) to R (relative to sR) is the function profR,sR[u]:R defined as follows:

profR,sR[u](s)=distG(u,s)distG(u,sR)for all sR.

Note that provided R is connected333A subset of vertices R of a graph G is connected if the induced subgraph G[R] is connected., we have profR,sR[u](s){|R|+1,|R|+1,,|R|2,|R|1}. Li and Parter [13] were first to study (a bit differently defined) distance profiles in the context of distance problems in planar graphs and provide a nontrivial bound on the number of possible distance profiles. Inspired by their ideas, Le and Wulff-Nilsen [12] proved that if R is connected and G is Kh-minor-free, then the set system

{{(s,i)R×{|R|+1,,|R|1}|iprofR,sR[u](s)}:uV(G)}

has VC dimension at most h1. Hence, by applying the Sauer-Shelah Lemma we obtain that

Theorem 3 ([12]).

For every integer h1, Kh-minor-free graph G, connected set RV(G), and sRR, there are at most 𝒪h(|R|2h2) different distance profiles to R relative to sR.

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 3 can be improved to a polynomial of degree independent of the parameter.

Theorem 4.

For every integer k1, (unweighted, undirected) graph G of Euler genus at most k, connected set RV(G), and sRR, the number of distance profiles to R relative to sR is at most 𝒪(k4|R|12).

The main idea behind the proof of Theorem 4 is the following simple observation: if P is a shortest path from some uV(G) to sR, then, as one walks along P from u to sR, 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 uV(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 4 would be possible even in the generality of Kh-minor-free graphs. Unfortunately, it seems that Theorem 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 Kh+2-minor-free).

Let 0<k be positive integers. Let R be a path of length and v1,,vk be k equidistant points on R (i.e., the distance between vi and vi+1 is at least p/(k1)). For every vector 𝐚=(a1,,ak){,,+p}k, construct a vertex u(𝐚) and, for every i{1,,k}, connect it with vi using a path of length ai. This finishes the construction of the graph G; see Figure 1 for an illustration. Note that G has treewidth at most k+1, because G{v1,,vk} is a forest. Furthermore, since the distance between consecutive vertices vi is at least p, we have that distG(u(𝐚),vi)=ai for every vector 𝐚 and i{1,,k}. Consequently, if we restrict to vectors 𝐚 with a1=, every vertex u(𝐚) has a different distance profile to R relative to v1. Finally, note that there are (p+1)k1(/(k1))k1=Ωk(k) different vectors 𝐚 with a1=, giving that many different profiles.

Figure 1: Illustration of a construction that shows that linear dependency on h in the exponent of the bound on the number of profiles is inevitable, even in graphs of treewidth h.

Our algorithm for Theorem 2 follows closely the approach of Le and Wulff-Nilsen [12] augmented by the bound provided by Theorem 4. Namely, we first compute an r-division of the input graph G into regions of size r=nδ, for some small δ>0. Then we use Theorem 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 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 5.

For every integers g,k1, there exists an algorithm that, given an (unweighted, undirected) n-vertex graph G and a set AV(G) such that |A|k and GA is of Euler genus at most g, runs in time 𝒪g,k(n2125logk1n) and computes the diameter of G and the eccentricity of every vertex of G.

Second, we show that Conjecture 1 holds for classes of graphs constructed by clique-sums of graphs as in Theorem 5. To state this result formally, we need some definitions. For a graph G, a tree decompostion of G is a pair (T,β) where T is a tree and β is a function that assigns to every tV(T) a bag β(t)V(G) such that (1) for every vV(G), the set {tV(T)|vβ(t)} is nonempty and connected in T, and (2) for every uvE(G) there exists tV(T) with u,vβ(t). The torso of the bag β(t) is constructed from G[β(t)] by adding, for every neighbor s of t in T, all edges between the vertices of β(s)β(t).

Theorem 6.

For every integer k1, 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,β) of G and a set A(t)β(t) for every tV(T) satisfying the following properties:

  • For every node tV(T), we have that |A(t)|k and the torso of β(t) with the vertices of A(t) deleted is a graph of Euler genus at most k.

  • For every edge stE(T), we have |β(s)β(t)|k.

The algorithm runs in time 𝒪k(n21356log6kn) and computes the diameter of G and the eccentricity of every vertex of G.

Note that the statements of Theorems 5 and 6 require the set A and the decomposition (T,β), 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,β) exist. At this point, we are not aware of any existing algorithm that would find in subquadratic time a set A as in Theorem 5, or the decomposition (T,β) with the sets A as in Theorem 6, even in the approximate sense. However, we were informed by Korhonen, Pilipczuk, Stamoulis, and Thilikos [11] that it seems likely that the techniques introduced in the recent almost linear-time algorithm for minor-testing [10] 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 5 and 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 [15]: every Kh-minor-free graph G admits a tree decomposition (T,β) such that

  • for every pair s,t of adjacent nodes of T, the set β(t)β(s) has size 𝒪h(1); and

  • the torso of every bag β(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 6) and a constant number of so-called vortices (which are not handled by Theorem 6). Thus, our methods fall short of verifying Conjecture 1 in full generality due to vortices.

We remark that recently, Thilikos and Wiederrecht [19] 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 [19] can be directly plugged into Theorem 6, with the caveat that [19] does not provide a subquadratic algorithm to compute the decomposition.

Coming back to Conjecture 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 𝒢k be the class of graphs defined as follows. We have G𝒢k if there exist two subgraphs G0,G1 of G and a sequence of vertices v1,,vb in V(G0)V(G1) such that:

  • V(G)=V(G0)V(G1),

  • E(G)=E(G0)E(G1),

  • G0 admits a planar embedding where the vertices v1,,vb lie on one face in this order, and

  • G1 admits a tree decomposition (T1,β1), where T1 is a path on nodes t1,,tb and for every i{1,,b}, the bag β1(ti) contains vi and is of size at most k.

It is easy to see that graphs from 𝒢k are Kk+𝒪(1)-minor-free. Do they satisfy Conjecture 1? That is, is there a constant c>0 such that the diameter problem in 𝒢k can be solved in time 𝒪k(n2c)?

Organization.

We prove Theorem 4 in Section 3. Theorem 5 is proven in Section 4; note that Theorem 2 follows from Theorem 5 for k=1. The proof of Theorem 6 can be found in the full version of the paper [9].

2 Preliminaries

Set systems and VC-dimension.

A set system is a collection of subsets of a given set A, which we call ground set of . We say that a subset YA is shattered by if {YS:S}=2Y, that is, the intersections of Y and the sets in contain every subset of Y. The VC-dimension of a set system with ground set A is the size of the largest subset YA shattered by . The notion of VC-dimension was introduced by Vapnik and Chervonenkis [20].

We will use the following well-known Sauer-Shelah Lemma [17, 18], which gives a polynomial upper bound on the size of a set system of bounded VC-dimension.

Lemma 7 (Sauer-Shelah Lemma).

Let be a set system with ground set A. If the VC-dimension of is at most k, then ||=𝒪(|A|k).

Basic graph notation.

All our graphs are undirected. For a graph G, the neighborhood of a vertex u is defined as NG(u)={v:uvE(G)} and for XV(G) we have NG(X)=uXNG(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 distG(u,v), is defined as the minimum length of a path in G with endpoints u and v. For every vV(G) and set RV(G), we set distG(v,R)min{distG(v,y):yR}. 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]{1,,q}. For a vertex vV(G) and a set XV(G), we define the X-eccentricity of v as eccX(v)maxxXdist(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 [14].

We will use the following result of Le and Wulff-Nilsen [12, Theorem 1.3] for planar graphs. Note that the set R is not necessarily connected.

Theorem 8.

Let h1 be an integer, G be a Kh-minor-free (unweighted, undirected) graph, R be a subset of V(G), and sRR. Then the set system

{{(s,i)R×|idistG(u,s)distG(u,sR)}:uV(G)}

has VC-dimension at most h1.

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 [21].

Theorem 9 ([21]).

Let V be a set of n points in d and let w:V be a weight function. By a suffix range, we mean any set of the form

𝖱𝖺𝗇𝗀𝖾(r1,,rd){(x1,,xd)dxiri for all i[d]}

for some range parameters r1,,rd.

There is a data structure that uses 𝒪(nlogd1n) preprocessing time, 𝒪(nlogd1n) memory and answers the following suffix range queries in time 𝒪(logd1n): given a tuple (ri)i[d], find the maximum value of w(v) over all vV𝖱𝖺𝗇𝗀𝖾(r1,,rd).

We will also need the following standard statement about r-divisions.

Theorem 10 ([22]).

Let G be a Kt-minor-free graph on n vertices. For any fixed constant ε>0, and for any parameter r with Ct2lognrn, where C is some absolute constant, we can construct in time 𝒪(n1+εr) an r-division of G, that is, a collection of connected subsets of vertices of G such that:

  • =V(G),

  • |R|r for every R, and

  • R|R|𝒪(nt/r), where R=RNG(V(G)R).

3 Distance profiles in graphs of bounded Euler genus

In this section we prove Theorem 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 [12]. The main idea behind the reduction is to consider certain notions of “extended” profiles, where the extension is built along a collection 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 4 is given at the end of this section.

3.1 Milestones

Let G be a graph, R be a subset of V(G), v0 be a vertex in V(G), and P be a shortest path from v0 to R. Let x be the endpoint of P in R. Further, let P be the linear ordering of the vertices traversed by P: for two vertices v,uV(P), we have vPu if u belongs to P[v,x]. We say that a vertex vV(P) is a milestone of P if either v=x or we have profR,x[v]profR,x[u], where u is the successor of v in P. We denote by MR(P) the set of all milestones of P. Given a milestone vMR(P), the neutral prefix of v in P is defined as the vertex set of the maximal subpath Q of P[v0,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 11.

Let G be a graph, R be a subset of V(G), v0 be a vertex in V(G) and P be a shortest path from v0 to R. Then for every vMR(P), every u in the neutral prefix of v, and every yR, it holds that dist(u,y)=|P[u,v]|+dist(v,y).

Proof.

Let x be the endpoint of P in R. Note that, by definition, profR,x[v]=profR,x[u]. Also, dist(u,x)=dist(u,v)+dist(v,x) and dist(u,v)=|P[u,v]|. Therefore, dist(u,y)=|P[u,v]|+dist(v,y) for every yR.

We also give an upper bound on the number of milestones.

Lemma 12.

Let G be a graph, R be a connected subset of V(G), v0 be a vertex of G, and P be a shortest path from v0 to R. Then the number of milestones of P is at most |R|2|R|+1.

Proof.

Let x be the endpoint of P in R. First observe that since P is a shortest path from v0 to R, we have dist(v,y)dist(v,x) for every vV(P) and every yR; hence profR,x[v](y)0. Also, since R is connected, for every yR we have profR,x[x](y)|R|1. To conclude the proof, it suffices to prove that for all v1,v2V(P) with v1Pv2, we have

profR,x[v1](y)profR,x[v2](y)for all yR. (1)

Indeed, (1) together with the previous observations shows that all the distinct distance profiles of the form profR,x[v] for vV(P) can be treated as vectors of length |R| with entries in {0,,|R|1}, and they all have distinct sums yRprofR,x[v](y). Since these sums range between 0 and |R|2|R|, the total number of distinct profiles is at most |R|2|R|+1, implying the same bound on the number of milestones.

To see why (1) holds, note that dist(v1,y)dist(v1,v2)+dist(v2,y) implies that

dist(v1,y)dist(v1,v2)+profR,x[v2](y)+dist(v2,x)=profR,x[v2](y)+dist(v1,x);

the last equality follows from P being a shortest path containing v1,v2, and x (in this order). This in turn implies that profR,x[v1](y)=dist(v1,y)dist(v1,x)profR,x[v2](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 𝒫 of paths in G is an R-shortest path collection if

  • every P𝒫 is a shortest path from some vPV(G) to R, i.e., |P|=dist(vP,R); and

  • RP𝒫V(P).

For each P𝒫, we denote by xP the endpoint of P in R. Note that the collection 𝒫 obtained by taking, for every yR, 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 P1,P2𝒫 and vV(P1)V(P2) it holds that P1[v,xP1]=P2[v,xP2]. 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 13.

Let G be a graph, R be a subset of vertices of G, and 𝒫 be an R-shortest path collection. Then for every two paths P1,P2𝒫 and every vV(P1)V(P2), we have |P1[v,xP1]|=|P2[v,xP2]|.

Anchor vertices and their prefixes.

Let G be a graph, R be a subset of V(G), and 𝒫 be an R-shortest path collection. We denote by H𝒫 the union of the paths in 𝒫, i.e., the graph (P𝒫V(P),P𝒫E(P)). We say that a vertex is an anchor vertex if either it has degree more than two in H𝒫 or it is a milestone of a path P𝒫. We denote by AR(P) the set of all anchor vertices lying on a path P𝒫 and by AR(𝒫) the set of all anchor vertices for 𝒫. Given a path P𝒫 with endpoints v0 and yR, and an anchor vertex wAR(P), the prefix of w in P is the vertex set of the maximal subpath Q of P[v0,w] satisfying the following: w is the only anchor vertex of P that belongs to Q. Note that for every anchor wV(P) there is a milestone w of P (possibly w=w) such that the prefix of w in P is a subset of the neutral prefix of w in P. Finally, for an anchor vertex w, the tail of w, denoted tail(w), is the subgraph of G consisting of the union of all prefixes of w in P over all paths P𝒫 that contain w.

Hat-distances.

Let G be a graph, R be a subset of vertices of G, and 𝒫 be an R-shortest path collection. We denote by

U𝒫V(G)P𝒫V(P).

For every uU𝒫, and every anchor vertex wAR(𝒫), we set

dist^(u,w)min{|Qu,z|+|P[z,w]|:P𝒫wV(P)z is in the prefix of w in P},

where Qu,z is a shortest path from u to z with all its internal vertices in U𝒫. If such Qu,z does not exist for any zV(tail(w)), we set dist^(u,w).

The following statement is a direct consequence of the definition of dist^(,).

Observation 14.

Let G be a graph, R be a subset of vertices of G, and 𝒫 be an R-shortest path collection. Then for every uU𝒫, we have that

dist(u,R)=min{dist^(u,w)+dist(w,R):wAR(𝒫)}.

Anchor-distance profiles.

Let G be a graph, R be a subset of vertices of G, and 𝒫 be an R-shortest path collection. The anchor-distance profile of a vertex uU𝒫 to R with respect to 𝒫 is a function profR,𝒫[u] mapping each wAR(𝒫) to

profR,𝒫[u](w)dist^(u,w)+dist(w,R)dist(u,R).

Observation 14 implies that we always have profR,𝒫[u](w)0. We set

prof^R,𝒫[u](w)min{profR,𝒫[u](w),|R|+1}.
Lemma 15.

Let G be a graph, let R be a connected subset of vertices of G, and sRR. Also, let 𝒫 be an R-shortest path collection. Then for all u1,u2U𝒫,

prof^R,𝒫[u1]=prof^R,𝒫[u2]impliesprofR,sR[u1]=profR,sR[u2].

Proof.

Fix u1,u2U𝒫 with prof^R,𝒫[u1]=prof^R,𝒫[u2]. We start by proving the following.

Claim 16.

Let uU𝒫 and yR. There is an anchor wAR(𝒫) such that

  • dist^(u,w)+dist(w,y)=dist(u,y) and

  • prof^R,𝒫[u](w)|R|.

Proof.

Let Q be a shortest path from u to y and let P𝒫 be the path which Q first intersects (if the first vertex of Q in P𝒫V(P) belongs to more than one paths in 𝒫, we choose P arbitrarily among these paths). Also, let u 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 in its prefix (in P). Note that uV(tail(w)).

We first show that

dist^(u,w)+dist(w,y)=dist(u,y). (2)

By Lemma 11 and the fact that |Q[u,y]|=dist(u,y), we have

dist(w,y)=|Q[u,y]||P[u,w]|. (3)

Also, by definition, we have

dist^(u,w)|Q[u,u]|+|P[u,w]|. (4)

By (3) and (4), we get that dist^(u,w)+dist(w,y)|Q|. Moreover, since Q is a shortest path from u to y and dist^(u,w)dist(u,w), we have

|Q|=dist(u,y)dist(u,w)+dist(w,y)dist^(u,w)+dist(w,y).

This proves (2).

Next, we show that prof^R,𝒫[u](w)|R|. Note that

profR,𝒫[u](w)+dist(u,R) =dist^(u,w)+dist(w,R)
dist^(u,w)+dist(w,y)=dist(u,y).

The connectivity of R implies that dist(u,y)dist(u,R)+|R|, which gives profR,𝒫[u](w)|R|, and the claim follows.

We next show that there is an integer c such that for every yR, we have

dist(u1,y)=dist(u2,y)+c.

Note that this will immediately imply that profR,sR[u1]=profR,sR[u2].

By Observation 14, for every h{1,2}, there is an anchor whAR(𝒫) such that dist(uh,R)=dist^(uh,wh)+dist(wh,R), which is equivalent to profR,𝒫[uh](wh)=0. If wh lies on Ph𝒫, then dist(uh,R)=dist(uh,xPh). Therefore, as profR,𝒫[u1]=profR,𝒫[u2], we can choose w1=w2 and P1=P2, hence xP1=xP2. In other words, there exists xR such that dist(u1,R)=dist(u1,x) and dist(u2,R)=dist(u2,x). We set cdist(u1,x)dist(u2,x)=dist(u1,R)dist(u2,R).

Now, fix yR. Let w1AR(P) be the anchor from Claim 16 (applied for u1 and y). As prof^R,𝒫[u1]=prof^R,𝒫[u2] and profR,𝒫[u1](w1)|R|, we get that profR,𝒫[u1](w1)=profR,𝒫[u2](w1), i.e.,

dist^(u1,w1)+dist(w1,R)dist(u1,R)=dist^(u2,w1)+dist(w1,R)dist(u2,R).

Therefore,

dist(u1,y) =dist^(u1,w1)+dist(w1,y)
=dist^(u2,w1)+dist(w1,y)+cdist(u2,y)+c;

the first equality follows from Claim 16. Thus dist(u2,y)+cdist(u1,y). A symmetric reasoning shows that also dist(u1,y)cdist(u2,y). Therefore we get dist(u1,y)=dist(u2,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 [14]. We say that a graph H embedded in a surface Σ is a simple cut-graph of Σ if H has a single face that is also homeomorphic to an open disk; equivalently, H has a single facial walk. Given a surface Σ and a simple cut-graph H on Σ, we denote by ΣH the surface obtained by cutting Σ along H. Note that, provided H is a simple cut-graph, ΣH is always a disk.

Suppose now that a graph G embedded on Σ and H is a subgraph of G that is a simple cut-graph of H. We define GH to be the graph embedded on ΣH obtained from G as follows. First, let σ be the (unique) facial walk of H and note that each edge e of H is contained exactly twice in σ and each vertex v of H is contained in σ as many times as the degree of v in H. To obtain GH, we replace H with a simple cycle Cσ 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 σ also prescribes for every edge uv of G between a vertex uV(G)V(H) and a vertex vV(H), to which copy of v in GH the vertex u should be adjacent to (in GH). See Figure 2 for an illustration.

Figure 2: Left: A graph G embedded on a surface Σ and a subgraph H of G (in blue) that is a simple cut-graph of Σ. Right: The graph GH embedded on the surface Σ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 17.

For every integer k1 and for every edge-weighted connected graph G embedded on a surface Σ of Euler genus at most k and every vertex uV(G), there is a subgraph H of G with the following properties:

  • H is a simple cut-graph of Σ, and

  • V(H) is the union of the vertex sets of 𝒪(k) shortest paths in G that have u as a common endpoint.

We are now ready to proceed to the proof of Theorem 4. Employing Lemma 15, 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 17.

Proof of Theorem 4.

We assume that G is connected – the distance profiles of all vertices that are not connected to R are equal. Let TR be a spanning tree of G[R] and let G0 be the graph obtained from G after contracting TR into a single vertex vR. Consider an embedding of G0 on a surface Σ of Euler genus at most k. By Lemma 17, there is a subgraph H0 of G0 that is a simple cut-graph of Σ and a family 𝒫0 of 𝒪(k) shortest paths in G0, each with vR as an endpoint, such that V(H0)=P𝒫0V(P). Furthermore, as Lemma 17 handles edge weights, we can slightly perturb the weights so that shortest paths in G0 are unique and, in particular, all shortest paths with one endpoint in vR form a tree. Since H0 is a simple cut-graph of Σ, G0H0 is disk-embedded. Uncontracting TR, we get a subgraph H of G such that GH is disk-embedded. Let 𝒫 be the family of projections of the paths of 𝒫0 onto G plus, for every yR, a zero-length path from y to y. Hence, 𝒫 is an R-shortest paths collection of size 𝒪(k) with V(𝒫)=V(H). Furthermore, since in G0 the paths of 𝒫0 formed a tree rooted at vR, 𝒫 is consistent.

Note that due to Lemma 12 we have that P𝒫|MR(P)|𝒪(k|R|2). Also, since 𝒫 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 𝒫, then |B||𝒫|1. Hence,

P𝒫|AR(P)|𝒪(k|R|2). (5)

We set 𝒯 be the set of all vertices of GH that are copies of the anchor vertices AR(𝒫). Since |𝒫|=𝒪(k), we can strengthen (5) to

|𝒯|=𝒪(k|R|2). (6)

For s𝒯, let w(s)AR() be the anchor vertex whose copy (in GH) is s. In the other direction, for wAR(), let S(w) be the set of copies of w in GH.

Let U be the set of vertices of GH that are not copies of vertices from H (i.e., U=V(G)V(H)). We set E𝗈𝗎𝗍 be the set of all edges uv of GH where uU and v is a copy of a vertex from H, i.e., vV(GH)U. We also set E𝗇𝖾𝗑𝗍 be the set of all edges uv of GH where u is a copy of an anchor vertex wAR(P) for some 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 G^ be the graph obtained from GH after the following modifications:

  • we subdivide |V(G)|-many times each edge in E𝗈𝗎𝗍E𝗇𝖾𝗑𝗍,

  • we introduce a new vertex t and add, for every s𝒯, a path between t and s of length

    dw(s),t|V(G)|+distG(w(s),R).

See Figure 3. Observe that since GH is disk-embedded, G^ is planar, because we may embed t together with all the added paths outside of the disk containing GH.

Figure 3: An illustration of (a part of) the construction of the graph 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 GH, while the paths obtained by subdividing the edges of E𝗈𝗎𝗍E𝗇𝖾𝗑𝗍 are depicted with dashed edges. Edges adjacent to t correspond to paths of appropriate length.

For every uU, we define a function π[u], mapping every wAR(𝒫) to

π[u](w)min{distG^(u,s):sS(w)}+dw,tdistG^(u,t).

Also, we set 𝒳^{X^uuU}, where for uU,

X^u{(w,i)AR(𝒫)×{0,,|R|+1}|iπ[u](w)}.
Claim 18.

The set system 𝒳^ has size 𝒪(k4|R|12).

Proof.

We set 𝒯+𝒯{t}. We start with the set system 𝒞1{Cu1:uU}, where

Cu1{(s,i)𝒯+×|idistG^(u,s)distG^(u,t)}.

As G^ is planar, by Theorem 8 we infer that 𝒞 has VC-dimension at most 4.

We now “shift columns” of 𝒞1. That is, define 𝒞2{Cu2:uU}, where

Cu2{(s,i)𝒯+×|idistG^(u,s)+dw(s),tdistG^(u,t)}.

Clearly, the VC-dimension of 𝒞1 and 𝒞2 are equal: a set Z𝒯+× shatters 𝒞1 if and only if the set {(s,dw(s),t+i):(s,i)Z} shatters 𝒞2.

Now, let 𝒞3 be “cropped” 𝒞2: 𝒞3{Cu3:uU}, where

Cu3Cu2(𝒯+×{0,,|R|+1}).

Since restricting to a smaller universe cannot increase VC-dimension, 𝒞3 has VC-dimension at most 4. Since |𝒯+|=𝒪(k|R|2), by Sauer-Shelah lemma (Lemma 7) we have |𝒞3|=𝒪(k4|R|12).

Now observe that for every u1,u2U

Cu13=Cu23impliesX^u1=X^u2. (7)

Indeed, the assumption Cu13=Cu23 implies that for every wAR(𝒫) and sS(W) we have

max(0,min(|R|+1,distG^(u1,s)+dw,tdistG^(u1,t)))
=max(0,min(|R|+1,distG^(u2,s)+dw,tdistG^(u2,t))).

For fixed wAR(𝒫), we take a minimum of the above expression over all sS(w), obtaining:

max(0,min(|R|+1,min{distG^(u1,s):sS(w)}+dw,tdistG^(u1,t)))
=max(0,min(|R|+1,min{distG^(u2,s):sS(w)}+dw,tdistG^(u2,t))).

This proves (7). From (7), we infer |𝒳^||𝒞3|=𝒪(k4|R|12), as desired.

We next relate the distance from a vertex uU to R (in G) and to t (in G^).

Claim 19.

For every uU, distG(u,R)=distG^(u,t)2|V(G)|.

Proof.

Fix uU. We first show that distG(u,R)distG^(u,t)2|V(G)|. For this, consider a shortest path Q^ in G^ from u to t. Observe that there is a vertex s𝒯 that is a copy of an anchor vertex w, such that Q^[s,t] is the path from s to t of length dw,t added in the construction of G^ from GH. Recall that dw,t=distG(w,R)+|V(G)|. Also, observe that Q^[u,s] contains at least one subdivided edge of E𝗈𝗎𝗍, as it starts in U and ends outside U, and otherwise corresponds to a walk from u to w in G. Therefore, we have

distG^(u,t)=|Q^| =|Q^[u,s]|+|Q^[s,t]|
=|Q^[u,s]|+distG(w,R)+|V(G)|
|V(G)|+distG(u,w)+distG(w,R)+|V(G)|
distG(u,R)+2|V(G)|.

We next show that distG(u,R)distG^(u,t)2|V(G)|. For this, consider a shortest path Q in G from u to R. Let yR be the endpoint of Q in R. Also, let z be the first vertex of Q (when ordering from u to y) in P𝒫V(P) and let 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,xP] (when ordering from z to xP) that is an anchor vertex. Observe that Q[u,z] corresponds to a path in G^ from u to a copy s of z that contains exactly one subdivided edge of E𝗈𝗎𝗍 (and no edge of E𝗇𝖾𝗑𝗍) and there is a copy of P[z,w] in G^ from s to a copy s of w that contains no edge of E𝗈𝗎𝗍E𝗇𝖾𝗑𝗍. Therefore,

|Q| =|Q[u,z]|+|Q[z,y]|
=|Q[u,z]|+|P[z,xP]|
(Q[z,y] and P[z,xP] being shortest paths from z to R)
=|Q[u,z]|+|P[z,w]|+|P[w,xP]|
=|Q[u,z]|+|P[z,w]|+distG(w,R)
(P being shortest path from a vertex vP to R)
distG^(u,s)|V(G)|+dw,t|V(G)|
distG^(u,t)2|V(G)|.

Thus, we have distG(u,R)=|Q|distG^(u,t)2|V(G)|, as desired.

Claim 20.

For every uU and wAR(𝒫), it holds that

dist^(u,w)< ifandonlyifdist^(u,w)=min{distG^(u,s):sS(w)}|V(G)|,
dist^(u,w)= ifandonlyifmin{distG^(u,s):sS(w)}>2|V(G)|.

Proof.

We first show that if dist^(u,w)<, then there exists sS(w) with distG^(u,s)|V(G)|+dist^(u,w). To this end, let Q be a path from u to w in G of length dist^(u,w), as in the definition of dist^(u,w). There exists P𝒫 with wAR(P) and a vertex zV(P)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, G^ contains a copy s of z such that Q[u,z] projects to a path from u to s with one subdivided edge of E𝗈𝗎𝗍 (and no edge of E𝗇𝖾𝗑𝗍) and also a copy of P[z,w] from s to a copy s of w with no subdivided edge of E𝗈𝗎𝗍E𝗇𝖾𝗑𝗍. The concatenation of these two paths witness that distG^(u,s)|V(G)|+dist^(u,w), as desired.

To finish the proof of the claim, it suffices to show that if there exists sS(w) with distG^(u,s)2|V(G)|, then dist^(u,w)distG^(u,s)|V(G)| (in particular, dist^(u,w)). To this end, let Q^ be a path in G^ from u to s of minimum length. Since uU but sU, Q^ necessarily contains at least one subdivided edge of E𝗈𝗎𝗍. Since |Q^|2|V(G)|, Q^ contains exactly one edge of E𝗈𝗎𝗍, no edge of E𝗇𝖾𝗑𝗍, and no edge incident with t. Consequently, there exists a vertex s on Q^ which is a copy of a vertex z that lies in the prefix of w on some path P𝒫 such that Q^ decomposes as Q^[u,s], which has all internal vertices in U, and Q^[s,s] going along a copy of P[z,w] to sS(w). Hence, Q^ corresponds to a path Q in G from u to w that satisfies the requirements of the definition of dist^(u,w) and witnesses dist^(u,w)|Q^||V(G)|, as desired.

This finishes the proof of the claim.

Using the two previous claims, we infer that for every uU and wAR(𝒫) it holds that

prof^R,𝒫[u](w)=min(|R|+1,π[u](w)). (8)

Indeed,

min(|R|+1,π[u](w))
=min(|R|+1,min{distG^(u,s):sS(w)}+dw,tdistG^(u,t))
=min(|R|+1,min{distG^(u,s):sS(w)}|V(G)|
+distG(w,R)distG(u,R))
by Claim 19
=min(|R|+1,dist^(u,w)+distG(w,R)distG(u,R))
by Claim 20
=prof^R,𝒫[u](w).

Here, in the third step we used the estimate distG(u,R)distG(w,R)|U||V(G)||R|, so if min{distG^(u,s):sS(w)}>2|V(G)| (which is equivalent to dist^(u,w)= by Claim 20), then the minimum is attained at value |R|+1.

For every uU, we set

Bu{(w,i)AR(𝒫)×|iprof^G,R[u](w)}.

Claim 18 and (8) imply that the set system {Bu:uU} has size 𝒪(k4|R|12).

Now, for every vV(G), we set

Sv{(s,i)R×{|R|,,|R|}|iprofR,sR[v](s)}.

The bound on the size of the set system {Bu:uU} and Lemma 15 imply that the size of {Su:uU} is bounded by 𝒪(k4|R|12). We conclude the proof of the lemma by bounding the size of {Su:uV(G)U}. For this, note that every vertex vV(G)U is either a milestone for some path P𝒫 or a vertex in the neutral prefix of a milestone. In the latter case, there is a path P𝒫 and a milestone wMR(P) such that Sv=Sw. Therefore, we have

|{Su:uV(G)U}|P𝒫|MR(P)|𝒪(k|R|2),

where the second inequality follows from (5). Hence, the size of {Sv:vV(G)} is at most |{Su:uU}|+|{Su:uV(G)U}|=𝒪(k4|R|12). This finishes the proof of Theorem 4.

4 Bounded Euler genus graphs with apices: proof of Theorem 5

In this section we prove Theorem 5. (Note that Theorem 2 is a special case of Theorem 5 for k=1.) We start by deriving the following corollary from Theorem 9.

Corollary 21.

Let V be a set of n points in d. There is a data structure that uses 𝒪(dnlogd2n) preprocessing time, 𝒪(dnlogd2n) memory and answers the following queries in time 𝒪(dlogd2n): given r1,,rd, find maxvVmini[d](vi+ri), where vi denotes the ith coordinate of v.

Proof.

Fix query parameters r1,,rd. Let λmaxvVmini[d](vi+ri) denote the answer we want to find.

We say that a pair (v,i)V×[d] is good if for every j[d], it holds that vjvirirj. Let

λ=max{vi+ri:i[d],vV, and (v,i) is good}.

We claim that

λ=λ. (9)

Let v=argmaxvV(mini[d]vi+ri) and let i=argmini[d]vi+ri. By the choice of i, for each j we have vj+rjvi+ri, implying vjvirirj. Hence (v,i) is good, so λvi+ri=λ.

On the other hand, consider a good pair (v,i) maximizing vi+ri. The goodness of (v,i) implies that i=argmini[d]vi+ri, hence λmini[d]vi+ri=vi+ri=λ. This proves (9).

For every i[d], we set Vi to be the set

{(v1vi,v2vi,,vi1vi,vi+1vi,,vdvi):vV}d1,

and set wi(v)vi. Let 𝔻i be the data structure obtained by applying Theorem 9 to Vi and wi. Consider the suffix range

Ri𝖱𝖺𝗇𝗀𝖾(rir1,rir2,,riri1,riri+1,,rird)d1.

Now, by (9) we have that

λ=max{ri+max{wi(v):vViRi}:i[d]}.

This value can be computed by asking d queries to the data structures 𝔻i, for i[d]. This gives us a data structure satisfying the conditions given in the lemma statement.

The main work in the proof of Theorem 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 10.

Lemma 22.

Fix constants 0<α,γ,ρ<1 and k. 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 AV(G) of size at most k, and a family with V(G)A= such that the following conditions are satisfied:

  • R|R|𝒪(nγ);

  • for every R, |R|𝒪(nρ) and G[R] is connected and contains O(|R|) edges; and

  • for every R, the number of distance profiles in GA on R is of 𝒪(nα).

Then, we can compute X-eccentricity of every vertex of G in time 𝒪(nγ+2ρlogn+(n1+γ+n1+α)logk1n).

Proof.

Let GGA and XXV(G). Denote A{a1,a2,,ak}. We first describe the procedure, and then discuss its time complexity.

For every aA and uV(G), we compute distance between a and u denoted dA(a,u).

Step 1.

We start by precomputing the following information for every region R. For all u,vR, we compute the distance between u and v in G[R], denoted dR(u,v). For all sR,uV(G), we compute the distance between s and u in G, denoted dR(u,s). We arbitrarily pick a pivot vertex sRR, and for brevity denote pR[u]profR,sR[u], where the profile is considered in G. That is, pR[u] is the (R)-profile of u with respect to sR:

pR[u](s)=dR(u,s)dR(u,sR),for all uV(G) and sR.

We define PR{pR[u]:uV(G)}. By our assumption, we have |PR|𝒪(nα). Finally, for every profile pPR, we list all vertices vXR such that pR[v]=p and set up the data structure of Corollary 21 for the points (dA(a1,v),,dA(ak,v),dRu(sR,v)); denote it by 𝔻R,p.

Step 2.

For every uV(G), we compute eccX(u) as follows. If uA, the answer is maxvXdA(u,v). Hence, we may assume uA. Let Ru denote any region of containing u. For every vRu, the shortest path from u to v in G either:

  • goes through an apex, in which case its length is minaAdA(a,u)+dA(a,v); or

  • is disjoint from A and intersects Ru, in which case its length is minsRudRu(s,u)+dRu(s,v); or

  • is contained entirely in Ru, in which case its length is dRu(u,v).

The length of this path is therefore the minimum among the three quantities. Using the above observation, we compute distG(u,v) explicitly for each vRu, and define ΔuRumaxvRuXdistG(u,v).

For every vV(G)(ARu), the shortest path between u and v either crosses A or Ru. The length of such path avoiding A is

minsRudRu(s,u)+dRu(s,v)=dRu(sR,v)+minsRu(dRu(s,u)+pRu[v](s)).

We partition the vertices v by their profile pRu[v] and for every pPRu, we compute the maximum distance to a vertex with profile p separately. Let Vp={vXRupRu[v]=p}. For every vVp, we have

distG(u,v)=min(minaAdA(a,u)+dA(a,v),dRu(sR,v)+minsRu(dRu(s,u)+p(s))).

We set ridA(a,u) for i[k], and rk+1minsRu(dRu(s,u)+p(s)). Now,

maxvVpdistG(u,v)=maxvVpmin(r1+dA(a1,v),,rk+dA(ak,v),rk+1+dRu(sR,v)).

This value can be computed by querying r1,,rk+1 to the data structure 𝔻Ru,p. We define ΔuV(G)(ARu) as the maximum of such values over all pPRu.

Finally, we set ΔuAmaxaAXdA(a,u), and report

eccX(u)=max(ΔuA,ΔuRu,ΔuV(G)(ARu)).

It remains to argue that this algorithm can be implemented in the desired running time. For any source uV(G), distance from u to all vertices of G can be calculated in time 𝒪((|V(G)|+|E(G)|)log|V(G)|) using Dijkstra’s algorithm. Therefore:

  • computing dA(a,) for all a can be done in time 𝒪(nlogn),

  • computing dR(,) for all R can be done in time 𝒪(nlognR|R|)𝒪(n1+γlogn),

  • computing dR(,) for all R can be done in time 𝒪(||n2ρlogn)𝒪(nγ+2ρlogn); constructing G[R] takes 𝒪(|R|2logn)=𝒪(n2ρlogn) time and calculating all pairs shortest paths can be done in time 𝒪(|R||E(G[R])|logn)=𝒪(n2ρlogn).

Finally, the total size of the data structures 𝔻R,p over all R,p is 𝒪(||n)=𝒪(n1+γ), hence we can construct them in time 𝒪(n1+γlogk1n).

Consider uV(G)A fixed in step 2. Computing ΔuRu takes 𝒪(|R||Ru|) time. Computing ΔuA can be done in constant time. Computing ΔuV(G)(ARu) requires asking |PRu| queries to some 𝔻R,p, which takes 𝒪(nαlogk1n) time in total. In total, step 2 for all vertices u can be done in time 𝒪(n1+αlogk1n+nρuV(G)A|Ru|)=𝒪(n1+αlogk1n+nγ+2ρ).

We conclude that the total running time is 𝒪(nγ+2ρlogn+(n1+γ+n1+α)logk1n).

The next statement is a reformulation of Theorem 5.

Theorem 23.

Fix constants k,g. Let 𝒞 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 𝒞, together with its set of apices A, computes the eccentricity of every vertex in time 𝒪k,g(n1+2425logk1n).

Proof.

Let A={a1,,ak} denote the set of apices and let G=GA. Fix ρ225. Since graphs of bounded genus exclude some fixed clique as a minor, by Theorem 10 (with ε=ρ/2) we can find an 𝒪(nρ)-division of G satisfying R|R|=𝒪(n1ρ2) in time 𝒪(n1+ρ) . By Theorem 4, the graph G has a degree 12 polynomial bound on the number of distance profiles. In particular, the number of profiles on every R is of 𝒪(|R|12)=𝒪(n12ρ). Let XV(G), γ1ρ2=2425 and α12ρ=2425. Now, applying Lemma 22 gives us an algorithm computing all eccentricities in time 𝒪(n1+2425logk1n).

References

  • [1] Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica, 68(2):287–311, 2014. doi:10.1007/S00453-012-9662-2.
  • [2] Sergio Cabello. Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. ACM Transactions on Algorithms, 15(2):21:1–21:38, 2019. doi:10.1145/3218821.
  • [3] Sergio Cabello and Christian Knauer. Algorithms for graphs of bounded treewidth via orthogonal range searching. Computational Geometry, 42(9):815–824, 2009. doi:10.1016/J.COMGEO.2009.02.001.
  • [4] Sergio Cabello, Éric Colin de Verdière, and Francis Lazarus. Algorithms for the edge-width of an embedded graph. Computational Geometry, 45(5):215–224, 2012. Special issue: 26th Annual Symposium on Computation Geometry at Snowbird, Utah, USA. doi:10.1016/j.comgeo.2011.12.002.
  • [5] Guillaume Ducoffe, Michel Habib, and Laurent Viennot. Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension. SIAM Journal on Computing, 51(5):1506–1534, 2022. doi:10.1137/20M136551X.
  • [6] Lech Duraj, Filip Konieczny, and Krzysztof Potępa. Better diameter algorithms for bounded VC-dimension graphs and geometric intersection graphs. In 32nd Annual European Symposium on Algorithms, ESA 2024, volume 308 of LIPIcs, pages 51:1–51:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024. doi:10.4230/LIPICS.ESA.2024.51.
  • [7] Jeff Erickson and Kim Whittlesey. Greedy optimal homotopy and homology generators. In Proc. of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, pages 1038–1046. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070581.
  • [8] Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann. Voronoi diagrams on planar graphs, and computing the diameter in deterministic O~(n5/3) time. SIAM Journal on Computing, 50(2):509–554, 2021. doi:10.1137/18M1193402.
  • [9] Kacper Kluk, Marcin Pilipczuk, Michał Pilipczuk, and Giannos Stamoulis. Faster diameter computation in graphs of bounded euler genus. CoRR, abs/2502.07501, 2025. doi:10.48550/arXiv.2502.07501.
  • [10] Tuukka Korhonen, Michał Pilipczuk, and Giannos Stamoulis. Minor Containment and Disjoint Paths in almost-linear time. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 53–61, 2024. doi:10.1109/FOCS61266.2024.00014.
  • [11] Tuukka Korhonen, Michał Pilipczuk, Giannos Stamoulis, and Dimitrios Thilikos, 2024. Private communication.
  • [12] Hung Le and Christian Wulff-Nilsen. VC set systems in minor-free (di)graphs and applications. In 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, pages 5332–5360. SIAM, 2024. doi:10.1137/1.9781611977912.192.
  • [13] Jason Li and Merav Parter. Planar diameter via metric compression. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 152–163. ACM, 2019. doi:10.1145/3313276.3316358.
  • [14] Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins series in the mathematical sciences. Johns Hopkins University Press, 2001. URL: https://jhupbooks.press.jhu.edu/title/graphs-surfaces.
  • [15] Neil Robertson and Paul D. Seymour. Graph Minors. XVI. Excluding a non-planar graph. Journal of Combinatorial Theory, Series B, 89(1):43–76, 2003. doi:10.1016/S0095-8956(03)00042-X.
  • [16] Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In 45th Symposium on Theory of Computing Conference, STOC 2013, pages 515–524. ACM, 2013. doi:10.1145/2488608.2488673.
  • [17] Norbert Sauer. On the density of families of sets. Journal of Combinatorial Theory, Series A, 13(1):145–147, 1972. doi:10.1016/0097-3165(72)90019-2.
  • [18] Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41(1):247–261, 1972. doi:10.2140/pjm.1972.41.247.
  • [19] Dimitrios M. Thilikos and Sebastian Wiederrecht. Killing a vortex. In 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2022, pages 1069–1080. IEEE, 2022. doi:10.1109/FOCS54457.2022.00104.
  • [20] V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264–280, 1971. doi:10.1137/1116025.
  • [21] Dan E. Willard. New data structures for orthogonal range queries. SIAM Journal on Computing, 14(1):232–253, 1985. doi:10.1137/0214019.
  • [22] Christian Wulff-Nilsen. Separator theorems for minor-free and shallow minor-free graphs with applications. CoRR, abs/1107.1292, 2011. arXiv:1107.1292.