Faster Diameter Computation in Graphs of Bounded Euler Genus
Abstract
We show that for any fixed integer , there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected -vertex graph of Euler genus at most in time
Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most after deletion of at most vertices, we show an algorithm for the same task that achieves the running time bound
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 -minor-free graphs, but the running time bound is for some constant depending on . That is, our savings in the exponent of the polynomial function of , as compared to the naive quadratic algorithm, are independent of the parameter .
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 graphsCategory:
Track A: Algorithms, Complexity and GamesCopyright and License:
![[Uncaptioned image]](x1.png)
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 pathsAcknowledgements:
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]](ERC2.jpg)
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Computing the diameter of an input (undirected, unweighted) graph is a classic computational problem that can be trivially solved in time111We follow the convention that the vertex and the edge count of the input graph are denoted by and , 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 and running in time , for any fixed , would break the Strong Exponential Time Hypothesis [16]. This motivates the search for restrictions on 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 -vertex planar graph can be computed in time; this complexity has been later improved by Gawrychowski, Kaplan, Mozes, Sharir, and Weimann to [8]222The notation hides factors polylogarithmic in , and the notation hides factors depending on a parameter .. A subsequent line of research [5, 6, 12] generalized this result to -minor-free graphs: for every integer , there exists a constant such that the diameter problem in -vertex -minor-free graphs can be solved in time . In the works [6, 12], it holds that ; 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 can be made a universal constant. That is, no known lower bound refutes the following conjecture:
Conjecture 1.
There exists a constant such that, for every integer , the diameter problem in (unweighted, undirected) -vertex -minor-free graphs can be solved in time .
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 . Recall here that the eccentricity of a vertex is defined as , where is the distance metric in .
Theorem 2.
For every integers , there exists an algorithm that, given an (unweighted, undirected) -vertex graph of Euler genus at most , runs in time and computes the diameter of and the eccentricity of every vertex of .
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 be a graph, be a subset of vertices, and be a vertex in . The distance profile of a vertex to (relative to ) is the function defined as follows:
Note that provided is connected333A subset of vertices of a graph is connected if the induced subgraph is connected., we have . 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 is connected and is -minor-free, then the set system
has VC dimension at most . Hence, by applying the Sauer-Shelah Lemma we obtain that
Theorem 3 ([12]).
For every integer , -minor-free graph , connected set , and , there are at most different distance profiles to relative to .
The VC dimension argument applied above inevitably leads to a bound with the exponent depending on . 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 , (unweighted, undirected) graph of Euler genus at most , connected set , and , the number of distance profiles to relative to is at most .
The main idea behind the proof of Theorem 4 is the following simple observation: if is a shortest path from some to , then, as one walks along from to , the distance profile of the current vertex to can only (point-wise) increase. A slightly more technical modification of this argument works for shortest paths from to . 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- 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 -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 in the exponent of the bound on the number of profiles is inevitable even in graphs of treewidth (which are -minor-free).
Let be positive integers. Let be a path of length and be equidistant points on (i.e., the distance between and is at least ). For every vector , construct a vertex and, for every , connect it with using a path of length . This finishes the construction of the graph ; see Figure 1 for an illustration. Note that has treewidth at most , because is a forest. Furthermore, since the distance between consecutive vertices is at least , we have that for every vector and . Consequently, if we restrict to vectors with , every vertex has a different distance profile to relative to . Finally, note that there are different vectors with , giving that many different profiles.
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 -division of the input graph into regions of size , for some small . Then we use Theorem 4 for individual regions to speed up the computation of distances between and , by grouping vertices outside according to their distance profiles to . 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 , there exists an algorithm that, given an (unweighted, undirected) -vertex graph and a set such that and is of Euler genus at most , runs in time and computes the diameter of and the eccentricity of every vertex of .
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 , a tree decompostion of is a pair where is a tree and is a function that assigns to every a bag such that (1) for every , the set is nonempty and connected in , and (2) for every there exists with . The torso of the bag is constructed from by adding, for every neighbor of in , all edges between the vertices of .
Theorem 6.
For every integer , there exists an algorithm with the following specification. The input consists of an (unweighted, undirected) -vertex graph together with a tree decomposition of and a set for every satisfying the following properties:
-
For every node , we have that and the torso of with the vertices of deleted is a graph of Euler genus at most .
-
For every edge , we have .
The algorithm runs in time and computes the diameter of and the eccentricity of every vertex of .
Note that the statements of Theorems 5 and 6 require the set and the decomposition , respectively, to be provided explicitly on input; this should be compared with more general statements where the algorithm is given only with a promise that such set or decomposition exist. At this point, we are not aware of any existing algorithm that would find in subquadratic time a set as in Theorem 5, or the decomposition with the sets 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 -minor-free graph admits a tree decomposition such that
-
for every pair of adjacent nodes of , the set has size ; and
-
the torso of every bag is “nearly embedable” into a surface of bounded (in terms of ) 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 , let be the class of graphs defined as follows. We have if there exist two subgraphs of and a sequence of vertices in such that:
-
,
-
,
-
admits a planar embedding where the vertices lie on one face in this order, and
-
admits a tree decomposition , where is a path on nodes and for every , the bag contains and is of size at most .
It is easy to see that graphs from are -minor-free. Do they satisfy Conjecture 1? That is, is there a constant such that the diameter problem in can be solved in time ?
Organization.
2 Preliminaries
Set systems and VC-dimension.
A set system is a collection of subsets of a given set , which we call ground set of . We say that a subset is shattered by if , that is, the intersections of and the sets in contain every subset of . The VC-dimension of a set system with ground set is the size of the largest subset 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 . If the VC-dimension of is at most , then .
Basic graph notation.
All our graphs are undirected. For a graph , the neighborhood of a vertex is defined as and for we have .
The length of a path , denoted , is the number of edges of . For two vertices of a graph , the distance between and , denoted , is defined as the minimum length of a path in with endpoints and . For every and set , we set For vertices appearing on a path , by we denote the subpath of with endpoints and . The set of vertices traversed by a path is denoted by . In all above notation, we sometimes drop the subscript if the graph is clear from the context.
For a nonnegative integer , we use the shorthand . For a vertex and a set , we define the -eccentricity of as . Thus, the eccentricity of in is the same as its -eccentricity.
The Euler genus of a graph is the minimum Euler characteristic of a surface, where 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 is not necessarily connected.
Theorem 8.
Let be an integer, be a -minor-free (unweighted, undirected) graph, be a subset of , and . Then the set system
has VC-dimension at most .
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 be a set of points in and let be a weight function. By a suffix range, we mean any set of the form
for some range parameters .
There is a data structure that uses preprocessing time, memory and answers the following suffix range queries in time : given a tuple , find the maximum value of over all .
We will also need the following standard statement about -divisions.
Theorem 10 ([22]).
Let be a -minor-free graph on vertices. For any fixed constant , and for any parameter with , where is some absolute constant, we can construct in time an -division of , that is, a collection of connected subsets of vertices of such that:
-
,
-
for every , and
-
, where .
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 be a graph, be a subset of , be a vertex in , and be a shortest path from to . Let be the endpoint of in . Further, let be the linear ordering of the vertices traversed by : for two vertices , we have if belongs to . We say that a vertex is a milestone of if either or we have , where is the successor of in . We denote by the set of all milestones of . Given a milestone , the neutral prefix of in is defined as the vertex set of the maximal subpath of satisfying the following: is the only milestone of that belongs to .
The next lemma shows that minimum-length paths towards that contain a vertex in the neutral prefix of a milestone can be assumed to pass through that milestone vertex.
Lemma 11.
Let be a graph, be a subset of , be a vertex in and be a shortest path from to . Then for every , every in the neutral prefix of , and every , it holds that .
Proof.
Let be the endpoint of in . Note that, by definition, . Also, and . Therefore, for every .
We also give an upper bound on the number of milestones.
Lemma 12.
Let be a graph, be a connected subset of , be a vertex of , and be a shortest path from to . Then the number of milestones of is at most .
Proof.
Let be the endpoint of in . First observe that since is a shortest path from to , we have for every and every ; hence . Also, since is connected, for every we have . To conclude the proof, it suffices to prove that for all with , we have
(1) |
Indeed, (1) together with the previous observations shows that all the distinct distance profiles of the form for can be treated as vectors of length with entries in , and they all have distinct sums . Since these sums range between and , the total number of distinct profiles is at most , implying the same bound on the number of milestones.
To see why (1) holds, note that implies that
the last equality follows from being a shortest path containing and (in this order). This in turn implies that , as claimed.
3.2 Anchor-distance profiles
Shortest path collections.
Let be a graph and be a subset of vertices of . We say that a collection of paths in is an -shortest path collection if
-
every is a shortest path from some to , i.e., ; and
-
.
For each , we denote by the endpoint of in . Note that the collection obtained by taking, for every , the zero-length path from to , is an -shortest path collection.
We say that an -shortest path collection is consistent if, for every and it holds that . That is, once two paths intersect, they continue together towards .
The following statement is a direct consequence of the definition of an -shortest path collection.
Observation 13.
Let be a graph, be a subset of vertices of , and be an -shortest path collection. Then for every two paths and every , we have .
Anchor vertices and their prefixes.
Let be a graph, be a subset of , and be an -shortest path collection. We denote by the union of the paths in , i.e., the graph . We say that a vertex is an anchor vertex if either it has degree more than two in or it is a milestone of a path . We denote by the set of all anchor vertices lying on a path and by the set of all anchor vertices for . Given a path with endpoints and , and an anchor vertex , the prefix of in is the vertex set of the maximal subpath of satisfying the following: is the only anchor vertex of that belongs to . Note that for every anchor there is a milestone of (possibly ) such that the prefix of in is a subset of the neutral prefix of in . Finally, for an anchor vertex , the tail of , denoted , is the subgraph of consisting of the union of all prefixes of in over all paths that contain .
Hat-distances.
Let be a graph, be a subset of vertices of , and be an -shortest path collection. We denote by
For every , and every anchor vertex , we set
where is a shortest path from to with all its internal vertices in . If such does not exist for any , we set .
The following statement is a direct consequence of the definition of .
Observation 14.
Let be a graph, be a subset of vertices of , and be an -shortest path collection. Then for every , we have that
Anchor-distance profiles.
Let be a graph, be a subset of vertices of , and be an -shortest path collection. The anchor-distance profile of a vertex to with respect to is a function mapping each to
Observation 14 implies that we always have . We set
Lemma 15.
Let be a graph, let be a connected subset of vertices of , and . Also, let be an -shortest path collection. Then for all ,
Proof.
Fix with . We start by proving the following.
Claim 16.
Let and . There is an anchor such that
-
and
-
.
Proof.
Let be a shortest path from to and let be the path which first intersects (if the first vertex of in belongs to more than one paths in , we choose arbitrarily among these paths). Also, let be the first vertex of (when ordering from to ) in and be the anchor of that contains in its prefix (in ). Note that .
We first show that
(2) |
By Lemma 11 and the fact that , we have
(3) |
Also, by definition, we have
(4) |
By (3) and (4), we get that . Moreover, since is a shortest path from to and , we have
This proves (2).
Next, we show that . Note that
The connectivity of implies that , which gives , and the claim follows.
We next show that there is an integer such that for every , we have
Note that this will immediately imply that .
By Observation 14, for every , there is an anchor such that , which is equivalent to . If lies on , then . Therefore, as , we can choose and , hence . In other words, there exists such that and . We set .
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 embedded in a surface is a simple cut-graph of if has a single face that is also homeomorphic to an open disk; equivalently, has a single facial walk. Given a surface and a simple cut-graph on , we denote by the surface obtained by cutting along . Note that, provided is a simple cut-graph, is always a disk.
Suppose now that a graph embedded on and is a subgraph of that is a simple cut-graph of . We define to be the graph embedded on obtained from as follows. First, let be the (unique) facial walk of and note that each edge of is contained exactly twice in and each vertex of is contained in as many times as the degree of in . To obtain , we replace with a simple cycle whose vertex set is the set of copies of vertices of and its edge set is the set of copies of edges of in the obvious way. Notice that also prescribes for every edge of between a vertex and a vertex , to which copy of in the vertex should be adjacent to (in ). See Figure 2 for an illustration.
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 and for every edge-weighted connected graph embedded on a surface of Euler genus at most and every vertex , there is a subgraph of with the following properties:
-
is a simple cut-graph of , and
-
is the union of the vertex sets of shortest paths in that have 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 is connected – the distance profiles of all vertices that are not connected to are equal. Let be a spanning tree of and let be the graph obtained from after contracting into a single vertex . Consider an embedding of on a surface of Euler genus at most . By Lemma 17, there is a subgraph of that is a simple cut-graph of and a family of shortest paths in , each with as an endpoint, such that . Furthermore, as Lemma 17 handles edge weights, we can slightly perturb the weights so that shortest paths in are unique and, in particular, all shortest paths with one endpoint in form a tree. Since is a simple cut-graph of , is disk-embedded. Uncontracting , we get a subgraph of such that is disk-embedded. Let be the family of projections of the paths of onto plus, for every , a zero-length path from to . Hence, is an -shortest paths collection of size with . Furthermore, since in the paths of formed a tree rooted at , is consistent.
Note that due to Lemma 12 we have that . Also, since is consistent, if are the vertices that are not in (recall that vertices in are milestones) and have degree more than two in the graph obtained by the union of the paths in , then . Hence,
(5) |
We set be the set of all vertices of that are copies of the anchor vertices . Since , we can strengthen (5) to
(6) |
For , let be the anchor vertex whose copy (in ) is . In the other direction, for , let be the set of copies of in .
Let be the set of vertices of that are not copies of vertices from (i.e., ). We set be the set of all edges of where and is a copy of a vertex from , i.e., . We also set be the set of all edges of where is a copy of an anchor vertex for some and is a copy of the neighbor of in that is not in the prefix of in .
Let now be the graph obtained from after the following modifications:
-
we subdivide -many times each edge in ,
-
we introduce a new vertex and add, for every , a path between and of length
See Figure 3. Observe that since is disk-embedded, is planar, because we may embed together with all the added paths outside of the disk containing .
For every , we define a function , mapping every to
Also, we set , where for ,
Claim 18.
The set system has size .
Proof.
We set . We start with the set system , where
As is planar, by Theorem 8 we infer that has VC-dimension at most 4.
We now “shift columns” of . That is, define , where
Clearly, the VC-dimension of and are equal: a set shatters if and only if the set shatters .
Now, let be “cropped” : , where
Since restricting to a smaller universe cannot increase VC-dimension, has VC-dimension at most . Since , by Sauer-Shelah lemma (Lemma 7) we have .
Now observe that for every
(7) |
Indeed, the assumption implies that for every and we have
For fixed , we take a minimum of the above expression over all , obtaining:
We next relate the distance from a vertex to (in ) and to (in ).
Claim 19.
For every , .
Proof.
Fix . We first show that . For this, consider a shortest path in from to . Observe that there is a vertex that is a copy of an anchor vertex , such that is the path from to of length added in the construction of from . Recall that . Also, observe that contains at least one subdivided edge of , as it starts in and ends outside , and otherwise corresponds to a walk from to in . Therefore, we have
We next show that . For this, consider a shortest path in from to . Let be the endpoint of in . Also, let be the first vertex of (when ordering from to ) in and let be the path that is contained (if is contained to more than one paths, pick one of them arbitrarily). Also, let be the first vertex of (when ordering from to ) that is an anchor vertex. Observe that corresponds to a path in from to a copy of that contains exactly one subdivided edge of (and no edge of ) and there is a copy of in from to a copy of that contains no edge of . Therefore,
( and being shortest paths from to ) | |||
( being shortest path from a vertex to ) | |||
Thus, we have , as desired.
Claim 20.
For every and , it holds that
Proof.
We first show that if , then there exists with . To this end, let be a path from to in of length , as in the definition of . There exists with and a vertex such that decomposes into and , with all internal vertices of in . Then, contains a copy of such that projects to a path from to with one subdivided edge of (and no edge of ) and also a copy of from to a copy of with no subdivided edge of . The concatenation of these two paths witness that , as desired.
To finish the proof of the claim, it suffices to show that if there exists with , then (in particular, ). To this end, let be a path in from to of minimum length. Since but , necessarily contains at least one subdivided edge of . Since , contains exactly one edge of , no edge of , and no edge incident with . Consequently, there exists a vertex on which is a copy of a vertex that lies in the prefix of on some path such that decomposes as , which has all internal vertices in , and going along a copy of to . Hence, corresponds to a path in from to that satisfies the requirements of the definition of and witnesses , as desired.
This finishes the proof of the claim.
Using the two previous claims, we infer that for every and it holds that
(8) |
Indeed,
by Claim 19 | ||
by Claim 20 | ||
Here, in the third step we used the estimate , so if (which is equivalent to by Claim 20), then the minimum is attained at value .
Now, for every , we set
The bound on the size of the set system and Lemma 15 imply that the size of is bounded by . We conclude the proof of the lemma by bounding the size of . For this, note that every vertex is either a milestone for some path or a vertex in the neutral prefix of a milestone. In the latter case, there is a path and a milestone such that . Therefore, we have
where the second inequality follows from (5). Hence, the size of is at most . 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 .) We start by deriving the following corollary from Theorem 9.
Corollary 21.
Let be a set of points in . There is a data structure that uses preprocessing time, memory and answers the following queries in time : given , find , where denotes the th coordinate of .
Proof.
Fix query parameters . Let denote the answer we want to find.
We say that a pair is good if for every , it holds that . Let
We claim that
(9) |
Let and let . By the choice of , for each we have , implying . Hence is good, so .
On the other hand, consider a good pair maximizing . The goodness of implies that , hence . This proves (9).
For every , we set to be the set
and set . Let be the data structure obtained by applying Theorem 9 to and . Consider the suffix range
Now, by (9) we have that
This value can be computed by asking queries to the data structures , for . 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 and . Assume we are given a connected graph on vertices with edges with positive integer weights, a subset of vertices , a subset of apices of size at most , and a family with such that the following conditions are satisfied:
-
;
-
for every , and is connected and contains edges; and
-
for every , the number of distance profiles in on is of .
Then, we can compute -eccentricity of every vertex of in time .
Proof.
Let and . Denote . We first describe the procedure, and then discuss its time complexity.
For every and , we compute distance between and denoted .
Step 1.
We start by precomputing the following information for every region . For all , we compute the distance between and in , denoted . For all , we compute the distance between and in , denoted . We arbitrarily pick a pivot vertex , and for brevity denote , where the profile is considered in . That is, is the -profile of with respect to :
We define . By our assumption, we have . Finally, for every profile , we list all vertices such that and set up the data structure of Corollary 21 for the points ; denote it by .
Step 2.
For every , we compute as follows. If , the answer is . Hence, we may assume . Let denote any region of containing . For every , the shortest path from to in either:
-
goes through an apex, in which case its length is ; or
-
is disjoint from and intersects , in which case its length is ; or
-
is contained entirely in , in which case its length is .
The length of this path is therefore the minimum among the three quantities. Using the above observation, we compute explicitly for each , and define .
For every , the shortest path between and either crosses or . The length of such path avoiding is
We partition the vertices by their profile and for every , we compute the maximum distance to a vertex with profile separately. Let . For every , we have
We set for , and . Now,
This value can be computed by querying to the data structure . We define as the maximum of such values over all .
Finally, we set , and report
It remains to argue that this algorithm can be implemented in the desired running time. For any source , distance from to all vertices of can be calculated in time using Dijkstra’s algorithm. Therefore:
-
computing for all can be done in time ,
-
computing for all can be done in time ,
-
computing for all can be done in time ; constructing takes time and calculating all pairs shortest paths can be done in time .
Finally, the total size of the data structures over all is , hence we can construct them in time .
Consider fixed in step 2. Computing takes time. Computing can be done in constant time. Computing requires asking queries to some , which takes time in total. In total, step 2 for all vertices can be done in time .
We conclude that the total running time is .
The next statement is a reformulation of Theorem 5.
Theorem 23.
Fix constants . Let denote the class of all graphs that can be obtained by taking a graph of Euler genus bounded by , and adding apices adjacent arbitrarily to the rest of and to each other. Then there is an algorithm that given an unweighted graph belonging to , together with its set of apices , computes the eccentricity of every vertex in time .
Proof.
Let denote the set of apices and let . Fix . Since graphs of bounded genus exclude some fixed clique as a minor, by Theorem 10 (with ) we can find an -division of satisfying in time . By Theorem 4, the graph has a degree polynomial bound on the number of distance profiles. In particular, the number of profiles on every is of . Let , and . Now, applying Lemma 22 gives us an algorithm computing all eccentricities in time .
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 -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 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.