pith. machine review for the scientific record. sign in

arxiv: 2605.10692 · v1 · submitted 2026-05-11 · 💻 cs.CG

Recognition: no theorem link

Charting the Diameter Computation Landscape on Intersection Graphs in the Plane

Timothy M. Chan , Hsien-Chih Chang , Jie Gao , S\'andor Kisfaludi-Bak , Hung Le , Da Wei Zheng
Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:58 UTC · model grok-4.3

classification 💻 cs.CG
keywords diameter computationintersection graphsunit disksline segmentsfat trianglescomputational geometryfine-grained complexitysubquadratic algorithms
0
0 comments X

The pith

The complexity of diameter computation in plane intersection graphs depends on a combination of object type, true diameter value, and intersection patterns.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Previous work suggested diameter computation was easy for some objects like unit disks but hard for others like segments under fine-grained assumptions. This paper shows the picture is far more irregular. Subquadratic algorithms exist for non-degenerate axis-aligned segments and for constant-diameter unit squares, while deciding diameter at most 2 remains hard for fat triangles and degenerate segments. The source of difficulty shifts depending on degeneracy and the actual diameter.

Core claim

Computing the diameter of geometric intersection graphs in the plane exhibits a nuanced complexity landscape where hardness arises from the interplay of object type, the true diameter value, and intersection configurations. For 2D objects this yields truly subquadratic algorithms for non-degenerate axis-aligned line segments, almost-linear time for constant-diameter unit squares, an improved Õ(n^{4/3}) algorithm for deciding unit-disk diameter at most 2, and conditional hardness for deciding diameter at most 2 on fat triangles and line segments.

What carries the argument

The dependence of running time on object degeneracy, the numerical value of the diameter, and specific intersection patterns when deciding or computing distances in geometric graphs.

If this is right

  • Non-degenerate axis-aligned line segment graphs admit truly subquadratic diameter algorithms, while degenerate instances become easier only when the diameter is a constant.
  • Unit-square intersection graphs with constant diameter can be solved in almost linear time, bypassing earlier VC-dimension barriers.
  • Deciding diameter exactly 2 in unit-disk graphs is possible in Õ(n^{4/3}) time.
  • Deciding diameter at most 2 is truly subquadratic-hard for both fat-triangle graphs and line-segment graphs under standard fine-grained assumptions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar parameterizations by diameter value may improve algorithms for other distance-based problems on geometric graphs.
  • The distinction between degenerate and non-degenerate instances could be relevant to related tasks such as all-pairs shortest paths in the same graph classes.

Load-bearing premise

The conditional hardness results for fat triangles and line segments rest on the Orthogonal Vectors hypothesis and related fine-grained assumptions remaining true.

What would settle it

Either a truly subquadratic algorithm for deciding whether the diameter of fat-triangle intersection graphs is at most 2, or a matching quadratic-time lower bound under an assumption weaker than Orthogonal Vectors.

Figures

Figures reproduced from arXiv: 2605.10692 by Da Wei Zheng, Hsien-Chih Chang, Hung Le, Jie Gao, S\'andor Kisfaludi-Bak, Timothy M. Chan.

Figure 1
Figure 1. Figure 1: (a) Two (vertex-disjoint) paths P and Q cross on the plane; their canonical (red) curves cross. (b) Two paths πG (vi j, ai ) (yellow) and πG (vcd , ac ) (blue) cross on the plane; in this figure, |πG (vi j, ac )| ≤ |πG (vi j, ai )|. Our starting point is the K5 -avoidance argument by Chang, Gao, and Le [CGL24] for showing that the distance VC-dimension of any intersection graph of pseudo-disks is at most 4… view at source ↗
Figure 2
Figure 2. Figure 2: Cases for the proof of Theorem 3.5. The blue and red paths indicate the canonical curves. In all cases, the horizontal segments lie on the same line, but have been drawn with a small gap in between for clarity. The predecessor/successor curves may not exist, or may also be horizontal, but we have drawn them as non-horizontal (if they exist) for clarity. or non-horizontal. We illustrate them as non-horizont… view at source ↗
Figure 3
Figure 3. Figure 3: Left: Two convex chains Cleft and Cright placed so that any segment connecting them remains disjoint from the interiors of their convex hulls (the red shaded regions). Right: Defining a group of k × k points along sAB, such that pAB(a, b) are grouped by the value of a, and groups have gaps of size ≃ |sAB|/k. is in (P0 \ P (k) 0 ) × ··· × (P∆ \ P (k) ∆ ). (In other words, if the sequence of x-coordinates in… view at source ↗
Figure 4
Figure 4. Figure 4: The construction of the intersection graph G ′ . Triangles on the left and right (red and blue) correspond to edges of G, crossing triangles (green) correspond to non-edges of G. The two gray triangles are the dummy triangles ∆left and ∆right. We can now prove the desired lower bound. Theorem 5.2. Assuming the 3-uniform 6-hyperclique hypothesis, there is no O(n 2−ϵ ) time algorithm for deciding if the inte… view at source ↗
Figure 5
Figure 5. Figure 5: (i) Placement of the segments sAB,sBC ,sCA. (ii) By choosing T large enough we ensure that the base of the half-square ∆ABF (a, b, f ) has angle O(ϵ) with the x-axis. (iii) The intersection of ∆ABF (a, b, f ) with the segment sF D. We need to ensure that ∆ABF (a, b, f ) remains disjoint from ∆DEF(d, e, f ′ ) for all f ′ ≠ f . (iv) The vertex u ′ of ∆ABF (a, b, f ) is on the arc of inscribed angle π/4 with… view at source ↗
Figure 6
Figure 6. Figure 6: Left: the segments sAB,sBA,sC D,sDC . Any segment connecting a left and right segment among them has angle at least φ with them. Right: placing the points pAB(a, b) along sAB. be distinct symbols among {A, B, C, D}. The pair {X, Y } is considered a crossing pair if {X, Y } has a non-empty intersection with both {A, B} and {C, D}. Let G ′ be the intersection graph of the following segments (see [PITH_FULL_… view at source ↗
Figure 7
Figure 7. Figure 7: (i) The construction with segments, with dummy segments in light blue. The segment hAD(a, d) (green) correspond￾ing to a crossing pair is lengthened beyond pAB(a, k) to cross all segments tAB(a, b) for all b ∈ [k]. (ii) Any segment tAB(a, b) has angle at least ψ = ∠v3 v1 v2 with both sAB and sBA. (iii) The two ends of the segment hAD(a, d) (the middle of this picture is distorted). Segment hAD(a, d) crosse… view at source ↗
Figure 8
Figure 8. Figure 8: (i) The construction of [BKK+22] for axis-aligned segments. (ii) We introduce a small rotation on the green segment sets (those of even index in the top row and odd index in the bottom row). The resulting intersection graph is identical to the one in [BKK+22], avoids degeneracies, and uses 3 different slopes. Proof: Let A, B ⊂ {0, 1} d be a set of n vectors each of dimension d = O(log n). We create the fol… view at source ↗
Figure 9
Figure 9. Figure 9: The flower Fp of a disk Dp centered at p. Proof: This is a simple consequence of a reduction of Bringmann et al. [BKK+22] for axis-aligned degenerate segments. Bringmann et al. [BKK+22] construct a set of axis-aligned segments that are grouped into several smaller independent sets, as depicted in [PITH_FULL_IMAGE:figures/full_fig_p024_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Any unit radius disk that intersects both A and B is stabbed by o. consider D = D′ as the base set of disks, and similarly we use Fp to denote the flower corresponding to some p ∈ A. The following lemma gives us an algorithm to check hop distances between points in two cells. Lemma 9.5. Let δ > 0 be a sufficiently small constant. Let A and B be two squares of side length δ such that 1 − 2 p 2δ ≤ dist(A, B… view at source ↗
Figure 11
Figure 11. Figure 11: The flowers {F ∗ p }p∈P are weak pseudo disks. p s y w R [PITH_FULL_IMAGE:figures/full_fig_p028_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The ray R starting from a point y with distance within 1/2 from the center p intersects ∂Fp only once. Remark 9.7. The above proof works for flowers defined as the union of convex, weak pseudodisks stabbed by the same point. For a point p, the flower Fp is not necessarily convex. Thus if we consider a point y inside Fp and shoot a ray from y, it may intersect ∂Fp multiple times. But if y is sufficiently c… view at source ↗
Figure 13
Figure 13. Figure 13: (i) The situation ruled out by Lemma 9.9. The flower intersection Fp ∩ Fq inside the half-plane U is depicted as the orange shaded region. Its boundary can be decomposed to parts that are contributed only by ∂Fp , only by ∂Fq (denoted by γp and γq ), or both (denoted by the curve γo ). The lemma claims that a point y ∈ γq cannot be below an overlap point x ∈ γo ∩ Hq . (ii) The impossible configuration: th… view at source ↗
Figure 14
Figure 14. Figure 14: The boundary ∂Fp implicitly represented by curves from canonical sets (shown in different colors). The boundary of one canonical set Ci is also shown. so we can also get an explicit list of V(∂Ci ) in clockwise order by computing the intersection point of consecutive arcs. We store the list of arcs (with indices) in an array. The time required to compute F is also O(n 4/3 log2 n). In the same amount of ti… view at source ↗
Figure 15
Figure 15. Figure 15: (Left) Crossing points of ∂ Fp and ∂ Fq inside cone CB . (Right) pq intersects cell B. Lemma 9.12 (Crossing points of ∂ Fp and ∂ Fq ). Given two points p and q in one grid cell A, either ∂Fp ∩ CB or ∂Fq ∩ CB is equal to the boundary ∂(Fp ∩ Fq ) ∩ CB , or there is some point a ∈ ∂(Fp ∩ Fq ) that is a point of some crossing or ghost overlap of ∂Fp and ∂Fq such that ∂(Fp ∩ Fq )∩CB is the concatenation of one… view at source ↗
Figure 16
Figure 16. Figure 16: (Left) ap and aq are not inside CB . (Right) ap and aq are both inside CB . one of ∂Fp ∩ CB or ∂Fq ∩ CB . If only ap falls in CB , then ∂(Fp ∩ Fq ) ∩ CB can be described in the claimed fashion with a = ap . If both fall in CB , ℓpq intersects CB . See [PITH_FULL_IMAGE:figures/full_fig_p033_16.png] view at source ↗
read the original abstract

Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainly depends on the object types: for unit disks and squares in 2D, the problem is solvable in truly subquadratic time, while for other objects, including unit segments and equilateral triangles in 2D or unit balls and axis-parallel unit cubes in 3D, there is no truly subquadratic time algorithm under the Orthogonal Vector (OV) hypothesis. We undertake a comprehensive study of computing the diameter of geometric intersection graphs for various types of objects. We discover many new irregularities, showing that the landscape is extremely nuanced: the source of hardness is a combination of the object type, the true diameter value, and how the objects intersect with each other. Our highlighted results for the 2D case include: 1. The diameter of non-degenerate, axis-aligned line segments can be computed in truly subquadratic time. Previous hardness result for line segments applies only to degenerate instances. On the other hand, for the degenerate case, we show that a truly subquadratic time algorithm exists when the true diameter is constant. 2. An almost-linear-time algorithm for unit-square graphs of constant diameter. Previous algorithms rely on succinct representation assuming bounded VC-dimension; for such a strategy $\Omega(n^{7/4})$ time is an inherent barrier. 3. An $\tilde{O}(n^{4/3})$-time algorithm to decide if the diameter of a unit-disk graph is at most 2. This improves upon the recent algorithm with running time $\tilde{O}(n^{2-1/9})$. 4. Deciding if the diameter of intersection graphs of fat triangles or line segments is at most 2 is truly subquadratic-hard under fine-grained complexity assumptions. Previous lower bounds only hold when deciding if diameter is at most 3.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

4 major / 3 minor

Summary. The manuscript presents a detailed investigation into the computational complexity of determining the diameter in intersection graphs of various types of geometric objects in the plane. It demonstrates that the complexity landscape is highly nuanced, influenced by the specific object types (such as axis-aligned line segments, unit squares, unit disks, fat triangles), the actual value of the diameter, and the nature of their intersections. The paper provides new algorithmic results, including truly subquadratic time for non-degenerate axis-aligned segments, almost-linear time for constant-diameter unit squares, and an improved Õ(n^{4/3}) time for deciding if unit-disk graph diameter is at most 2, alongside conditional lower bounds under the Orthogonal Vectors hypothesis for certain cases with diameter at most 2.

Significance. If the results hold, this work significantly advances the understanding of diameter computation on geometric intersection graphs by carving out previously unseparated regimes based on object type, diameter value, and degeneracy. The explicit use of standard fine-grained assumptions (OV hypothesis) for lower bounds and the separation of degenerate vs. non-degenerate cases for segments provide clear, falsifiable distinctions. No machine-checked proofs or code are mentioned, but the concrete running-time improvements and reductions strengthen the contribution to fine-grained geometric complexity.

major comments (4)
  1. [Result 1] Result 1 (non-degenerate axis-aligned segments): the claim that previous hardness applies only to degenerate instances is load-bearing for the subquadratic upper bound; the manuscript must explicitly define 'non-degenerate' (e.g., minimum intersection angle or separation) and prove that the algorithm fails or slows on near-degenerate inputs that still satisfy the definition.
  2. [Result 2] Result 2 (constant-diameter unit squares): the almost-linear algorithm bypasses the Ω(n^{7/4}) VC-dimension barrier cited for succinct representations; the proof should include a concrete running-time analysis showing how the constant-diameter assumption is used to achieve o(n^{7/4}) without relying on bounded VC-dimension.
  3. [Result 3] Result 3 (unit-disk diameter ≤2): the improvement to Õ(n^{4/3}) from prior Õ(n^{2-1/9}) is central; the manuscript should state whether the new exponent is tight under OV or 3SUM and include a brief comparison table of exponents for diameter 2 vs. larger constants.
  4. [Hardness results] Hardness for diameter ≤2 on fat triangles/segments: the reductions must ensure that the constructed instances have diameter exactly 2 (not larger) while preserving fatness and planarity; any slack in the reduction could allow a subquadratic algorithm for the exact diameter-2 case.
minor comments (3)
  1. The abstract repeatedly uses 'truly subquadratic'; add a brief parenthetical or footnote defining it as O(n^{2-ε}) for some ε>0 to avoid ambiguity with weakly subquadratic bounds.
  2. Prior running times (e.g., Õ(n^{2-1/9}) for unit disks) should be cited explicitly in the abstract or introduction rather than left as 'recent algorithm'.
  3. Figure captions or a summary table comparing all new vs. prior bounds across object types and diameter values would improve readability.

Simulated Author's Rebuttal

4 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment, and recommendation for minor revision. We address each major comment point by point below, providing clarifications and committing to revisions where appropriate.

read point-by-point responses

  1. Referee: [Result 1] Result 1 (non-degenerate axis-aligned segments): the claim that previous hardness applies only to degenerate instances is load-bearing for the subquadratic upper bound; the manuscript must explicitly define 'non-degenerate' (e.g., minimum intersection angle or separation) and prove that the algorithm fails or slows on near-degenerate inputs that still satisfy the definition.

    Authors: We agree a precise definition is required. In the revision we will explicitly define non-degenerate axis-aligned segments as those in which all intersections occur in the relative interiors of both segments and the minimum Euclidean distance between any two non-intersecting segments is bounded below by a positive constant (or, equivalently, no three segments meet at a single point). The subquadratic algorithm relies on this separation to prune candidate pairs via a sweep that avoids quadratic dense-intersection subproblems; we will add a short lemma showing that if the minimum separation tends to zero the running time degrades toward quadratic, matching the known hardness for degenerate instances. This makes the distinction rigorous without altering the stated result. revision: yes

  2. Referee: [Result 2] Result 2 (constant-diameter unit squares): the almost-linear algorithm bypasses the Ω(n^{7/4}) VC-dimension barrier cited for succinct representations; the proof should include a concrete running-time analysis showing how the constant-diameter assumption is used to achieve o(n^{7/4}) without relying on bounded VC-dimension.

    Authors: We will expand the proof to contain an explicit running-time calculation. The constant-diameter assumption partitions the arrangement into O(1) regions (by fixing a constant number of possible “center” squares that realize the diameter) and permits a linear-time sweep or divide-and-conquer within each region; the total cost is O(n log n). This geometric partitioning argument never invokes VC-dimension or succinct representations, thereby circumventing the Ω(n^{7/4}) barrier. The revised proof will spell out the recurrence and the O(1) region count. revision: yes

  3. Referee: [Result 3] Result 3 (unit-disk diameter ≤2): the improvement to Õ(n^{4/3}) from prior Õ(n^{2-1/9}) is central; the manuscript should state whether the new exponent is tight under OV or 3SUM and include a brief comparison table of exponents for diameter 2 vs. larger constants.

    Authors: We will add a short paragraph stating that the Õ(n^{4/3}) exponent is not known to be tight under the Orthogonal Vectors or 3SUM hypotheses; it improves the previous bound but may still admit further improvement. We will also insert a small comparison table listing the best known exponents for deciding whether the diameter is at most 2 versus at most k for small constant k, thereby highlighting the special algorithmic structure available only for the diameter-2 case. revision: yes

  4. Referee: [Hardness results] Hardness for diameter ≤2 on fat triangles/segments: the reductions must ensure that the constructed instances have diameter exactly 2 (not larger) while preserving fatness and planarity; any slack in the reduction could allow a subquadratic algorithm for the exact diameter-2 case.

    Authors: The reductions are constructed so that a yes-instance of Orthogonal Vectors produces an intersection graph of diameter exactly 2, while a no-instance produces diameter at least 3. We will add an explicit paragraph verifying that (i) fatness is preserved (all triangles have angles bounded away from zero by a fixed constant), (ii) the geometric objects remain in the plane without introducing extraneous intersections, and (iii) the diameter is controlled precisely by the reduction mapping. Because the mapping is direct and gap-preserving, no slack exists that would permit a subquadratic algorithm for the exact diameter-2 problem. revision: yes

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's core contributions consist of new subquadratic algorithms (e.g., for non-degenerate axis-aligned segments and constant-diameter unit squares) and improved bounds (e.g., Õ(n^{4/3}) for unit-disk diameter ≤2), together with OV-based hardness reductions for diameter ≤2 on fat triangles and segments. These derivations rely on external fine-grained hypotheses and prior geometric results rather than any self-definitional equivalence, fitted parameter renamed as prediction, or load-bearing self-citation chain. The nuanced distinctions among object types, diameter values, and degeneracy patterns are established by explicit algorithmic constructions and reductions that remain independently falsifiable against the stated external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results rest on standard fine-grained complexity assumptions and basic geometric intersection properties; no new free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Orthogonal Vectors hypothesis
    Invoked for the hardness results on line segments, fat triangles, and related objects as described in the abstract.

pith-pipeline@v0.9.0 · 5676 in / 1240 out tokens · 71497 ms · 2026-05-12T04:58:47.764045+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

168 extracted references · 168 canonical work pages

  1. [1]

    40th International Symposium on Computational Geometry (SoCG) , author =

    A Clique-Based Separator for Intersection Graphs of Geodesic Disks in. 40th International Symposium on Computational Geometry (SoCG) , author =. 2024 , volume =

    work page 2024

  2. [2]

    2021 , month = dec, journal =

    Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs , author =. 2021 , month = dec, journal =. doi:10.1007/s00454-021-00327-y , langid =

    work page doi:10.1007/s00454-021-00327-y 2021

  3. [3]

    2021 , journal =

    Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs , author =. 2021 , journal =

    work page 2021

  4. [4]

    and Cohen, Ravid and Halperin, Dan and Mulzer, Wolfgang , year =

    Agarwal, Pankaj K. and Cohen, Ravid and Halperin, Dan and Mulzer, Wolfgang , year =. Dynamic Maintenance of the Lower Envelope of Pseudo-Lines , booktitle =

    work page

  5. [5]

    2000 , pages =

    Handbook of Computational Geometry , author =. 2000 , pages =. doi:10.1016/B978-044482537-7/50002-4 , isbn =

    work page doi:10.1016/b978-044482537-7/50002-4 2000

  6. [6]

    1999 , _month = jan, journal =

    Fast Estimation of Diameter and Shortest Paths (without Matrix Multiplication) , author =. 1999 , _month = jan, journal =

    work page 1999

  7. [7]

    A Refined Laser Method and Faster Matrix Multiplication , booktitle =

    Alman, Josh and Williams, Virginia Vassilevska , year =. A Refined Laser Method and Faster Matrix Multiplication , booktitle =

    work page

  8. [8]

    More Asymmetry Yields Faster Matrix Multiplication , booktitle =

    Alman, Josh and Duan, Ran and Williams, Virginia Vassilevska and Xu, Yinzhan and Xu, Zixuan and Zhou, Renfei , year =. More Asymmetry Yields Faster Matrix Multiplication , booktitle =

    work page

  9. [9]

    Alon, Noga and Brightwell, Graham and Kierstead, H. A. and Kostochka, A. V. and Winkler, Peter , year =. Dominating Sets in. Journal of Combinatorial Theory , volume =. doi:10.1016/j.jctb.2005.09.003 , keywords =

    work page doi:10.1016/j.jctb.2005.09.003 2005

  10. [10]

    and Peleg, David and West, Douglas , year =

    Alon, Noga and Karp, Richard M. and Peleg, David and West, Douglas , year =. A Graph-Theoretic Game and Its Application to the. SIAM Journal on Computing , volume =

    work page

  11. [11]

    2021 , month = jan, journal =

    On Pseudo-Disk Hypergraphs , author =. 2021 , month = jan, journal =

    work page 2021

  12. [12]

    1998 , journal =

    The Discrete 2-Center Problem , author =. 1998 , journal =

    work page 1998

  13. [13]

    1985 , journal =

    Complexity of Network Synchronization , author =. 1985 , journal =

    work page 1985

  14. [14]

    2024 , _month = jan, journal =

    Dynamic Connectivity in Disk Graphs , author =. 2024 , _month = jan, journal =. doi:10.1007/s00454-023-00621-x , langid =

    work page doi:10.1007/s00454-023-00621-x 2024

  15. [15]

    2020 , journal =

    A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs , author =. 2020 , journal =

    work page 2020

  16. [16]

    2024 , month = oct, number =

    Quasilinear-Time Eccentricities Computation, and More, on Median Graphs , author =. 2024 , month = oct, number =. 2410.10235 , publisher =

    work page arXiv 2024

  17. [17]

    doi:10.48550/ARXIV.2410.17197 , author =

    Upper bounds for multicolour Ramsey numbers , publisher =. doi:10.48550/ARXIV.2410.17197 , author =

    work page doi:10.48550/arxiv.2410.17197

  18. [18]

    2023 , month = jan, number =

    Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs , author =. 2023 , month = jan, number =. 2110.02709 , primaryclass =

    work page arXiv 2023

  19. [19]

    Faster Approximation of Distances in Graphs , booktitle =

    Berman, Piotr and Kasiviswanathan, Shiva Prasad , year =. Faster Approximation of Distances in Graphs , booktitle =

    work page

  20. [20]

    Compositio Mathematica , volume=

    A combinatorial problem in geometry , author=. Compositio Mathematica , volume=

    work page

  21. [21]

    2023 , journal =

    Clique-Based Separators for Geometric Intersection Graphs , author =. 2023 , journal =

    work page 2023

  22. [22]

    Negative-Weight Single-Source Shortest Paths in near-Linear Time , booktitle =

    Bernstein, Aaron and Nanongkai, Danupon and. Negative-Weight Single-Source Shortest Paths in near-Linear Time , booktitle =. 2022 , pages =

    work page 2022

  23. [23]

    4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-Hard at Time

    Bonnet,. 4 vs 7 Sparse Undirected Unweighted Diameter Is SETH-Hard at Time. 2022 , month = mar, journal =. doi:10.1145/3494540 , keywords =

    work page doi:10.1145/3494540 2022

  24. [24]

    2015 , journal =

    Identifying Codes in Hereditary Classes of Graphs and VC-Dimension , author =. 2015 , journal =. https://doi.org/10.1137/14097879X , pages =

    work page doi:10.1137/14097879x 2015

  25. [25]

    2012 , month = jul, journal =

    Scott's Induced Subdivision Conjecture for Maximal Triangle-Free Graphs , author =. 2012 , month = jul, journal =. doi:10.1017/S0963548312000065 , keywords =

    work page doi:10.1017/s0963548312000065 2012

  26. [26]

    2015 , journal =

    Bousquet, Nicolas and Thomass. 2015 , journal =

    work page 2015

  27. [27]

    2015 , month = dec, journal =

    Bousquet, Nicolas and Thomass. 2015 , month = dec, journal =. doi:10.1016/j.disc.2015.05.026 , keywords =

    work page doi:10.1016/j.disc.2015.05.026 2015

  28. [28]

    2024 , month = sep, number =

    An \ 11/6\ -Approximation Algorithm for Vertex Cover on String Graphs , author =. 2024 , month = sep, number =. arXiv , langid =:2409.18820 , primaryclass =

    work page arXiv 2024

  29. [29]

    1996 , month = apr, langid =

    Algorithmic Aspects of Constrained Unit Disk Graphs , author =. 1996 , month = apr, langid =

    work page 1996

  30. [30]

    Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs , booktitle =

    Bringmann, Karl and. Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs , booktitle =. 2022 , _month = jun, pages =

    work page 2022

  31. [31]

    2013 , journal =

    Topological Hypergraphs , author =. 2013 , journal =

    work page 2013

  32. [32]

    2015 , _month = may, journal =

    Shortest Paths in Intersection Graphs of Unit Disks , author =. 2015 , _month = may, journal =. doi:10.1016/j.comgeo.2014.12.003 , keywords =

    work page doi:10.1016/j.comgeo.2014.12.003 2015

  33. [33]

    2018 , month = dec, journal =

    Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs , author =. 2018 , month = dec, journal =

    work page 2018

  34. [34]

    Practical Computation of Graph VC-Dimension , booktitle =

    Coudert, David and Csik. Practical Computation of Graph VC-Dimension , booktitle =. 2024 , pages =

    work page 2024

  35. [35]

    Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs , booktitle =

    Chang, Hsien-Chih and Gao, Jie and Le, Hung , year =. Computing Diameter+2 in Truly-Subquadratic Time for Unit-Disk Graphs , booktitle =. doi:10.4230/LIPIcs.SoCG.2024.38 , note =

    work page doi:10.4230/lipics.socg.2024.38 2024

  36. [36]

    , year =

    Chan, Timothy M. , year =. All-Pairs Shortest Paths for Unweighted Undirected Graphs in. ACM Transactions on Algorithms , volume =

    work page

  37. [37]

    and Skrepetos, Dimitrios , year =

    Chan, Timothy M. and Skrepetos, Dimitrios , year =. All-Pairs Shortest Paths in Unit-Disk Graphs in Slightly Subquadratic Time , booktitle =

    work page

  38. [38]

    and Skrepetos, Dimitrios , year =

    Chan, Timothy M. and Skrepetos, Dimitrios , year =. All-Pairs Shortest Paths in Geometric Intersection Graphs , booktitle =

    work page

  39. [39]

    Chan and Dimitrios Skrepetos , title =

    Timothy M. Chan and Dimitrios Skrepetos , title =. J. Comput. Geom. , volume =. 2019 , _url =. doi:10.20382/JOCG.V10I1A2 , timestamp =

    work page doi:10.20382/jocg.v10i1a2 2019

  40. [40]

    2019 , month = aug, journal =

    Faster Approximate Diameter and Distance Oracles in Planar Graphs , author =. 2019 , month = aug, journal =

    work page 2019

  41. [41]

    2019 , journal =

    Approximate Shortest Paths and Distance Oracles in Weighted Unit-Disk Graphs , author =. 2019 , journal =

    work page 2019

  42. [42]

    2023 , journal =

    Almost Optimal Exact Distance Oracles for Planar Graphs , author =. 2023 , journal =

    work page 2023

  43. [43]

    Fractional Cascading:

    Chazelle, Bernard and Guibas, Leonidas J , year =. Fractional Cascading:. Algorithmica , volume =

    work page

  44. [44]

    Filtering Search: A New Approach to Query-Answering , booktitle =

    Chazelle, Bernard , year =. Filtering Search: A New Approach to Query-Answering , booktitle =. doi:10.1109/SFCS.1983.17 , keywords =

    work page doi:10.1109/sfcs.1983.17 1983

  45. [45]

    1986 , _url =

    Bernard Chazelle , title =. 1986 , _url =. doi:10.1137/0215051 , timestamp =

    work page doi:10.1137/0215051 1986

  46. [46]

    and Roditty, Liam and Schoenebeck, Grant and Tarjan, Robert E

    Chechik, Shiri and Larkin, Daniel H. and Roditty, Liam and Schoenebeck, Grant and Tarjan, Robert E. and Williams, Virginia Vassilevska , year =. Better Approximation Algorithms for the Graph Diameter , booktitle =

    work page

  47. [47]

    Approximate Distance Oracles with Constant Query Time , booktitle =

    Chechik, Shiri , year =. Approximate Distance Oracles with Constant Query Time , booktitle =

    work page

  48. [48]

    Approximate Distance Oracles with Improved Bounds , booktitle =

    Chechik, Shiri , year =. Approximate Distance Oracles with Improved Bounds , booktitle =

    work page

  49. [49]

    Parallel and Distributed Expander Decomposition: Simple, Fast, and near-Optimal , booktitle =

    Chen, Daoyuan and Meierhans, Simon and Gutenberg, Maximilian Probst and Saranurak, Thatchaphol , year =. Parallel and Distributed Expander Decomposition: Simple, Fast, and near-Optimal , booktitle =

    work page

  50. [50]

    2007 , journal =

    Covering Planar Graphs with a Fixed Number of Balls , author =. 2007 , journal =

    work page 2007

  51. [51]

    2007 , month = feb, journal =

    Covering Planar Graphs with a Fixed Number of Balls , author =. 2007 , month = feb, journal =. doi:10.1007/s00454-006-1260-0 , langid =

    work page doi:10.1007/s00454-006-1260-0 2007

  52. [52]

    2020 , month = mar, number =

    Further Results on Colored Range Searching , author =. 2020 , month = mar, number =. doi:10.48550/arXiv.2003.11604 , urldate =. 2003.11604 , primaryclass =

    work page doi:10.48550/arxiv.2003.11604 2020

  53. [53]

    Charting the Diameter Computation Landscape on Intersection Graphs in

    Anonymous Author(s) , year =. Charting the Diameter Computation Landscape on Intersection Graphs in

    work page

  54. [54]

    Charting the Diameter Computation Landscape of Intersection Graphs in

    Anonymous Author(s) , year =. Charting the Diameter Computation Landscape of Intersection Graphs in

    work page

  55. [55]

    Chan and Qizheng He and Yakov Nekrich , _editor =

    Timothy M. Chan and Qizheng He and Yakov Nekrich , _editor =. Further Results on Colored Range Searching , booktitle =. 2020 , _url =. doi:10.4230/LIPICS.SOCG.2020.28 , timestamp =

    work page doi:10.4230/lipics.socg.2020.28 2020

  56. [56]

    Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture

    Almost-Linear. Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , author =. 2022 , series =. doi:10.1145/3519935.3519998 , isbn =

    work page doi:10.1145/3519935.3519998 2022

  57. [57]

    2017 , month = oct, pages =

    Fast and Compact Exact Distance Oracle for Planar Graphs , booktitle =. 2017 , month = oct, pages =

    work page 2017

  58. [58]

    Quasi-Optimal Range Searching in Spaces of Finite

    Chazelle, Bernard and Welzl, Emo , year =. Quasi-Optimal Range Searching in Spaces of Finite. Discrete & Computational Geometry , volume =. doi:10.1007/BF02187743 , langid =

    work page doi:10.1007/bf02187743

  59. [59]

    2015 , month = sep, journal =

    Algorithmic Applications of Baur-Strassen's Theorem , author =. 2015 , month = sep, journal =. doi:10.1145/2736283 , langid =

    work page doi:10.1145/2736283 2015

  60. [60]

    , editor =

    Lee, James R. , editor =. Separators in Region Intersection Graphs , booktitle =. 2017 , series =. doi:10.4230/LIPIcs.ITCS.2017.1 , bibsource =

    work page doi:10.4230/lipics.itcs.2017.1 2017

  61. [61]

    and Ducoffe, Guillaume , year =

    Dragan, Feodor F. and Ducoffe, Guillaume , year =. Algorithmica. An International Journal in Computer Science , volume =

    work page

  62. [62]

    2021 , journal =

    A Story of Diameter, Radius, and (Almost) Helly Property , author =. 2021 , journal =. doi:10.1002/net.21998 , urldate =

    work page doi:10.1002/net.21998 2021

  63. [63]

    2025 , month = jan, eprint =

    Certificates in P and Subquadratic-Time Computation of Radius, Diameter, and All Eccentricities in Graphs , author =. 2025 , month = jan, eprint =. doi:10.1137/1.9781611978322.70 , urldate =

    work page doi:10.1137/1.9781611978322.70 2025

  64. [64]

    2023 , journal =

    A Note on Reachability and Distance Oracles for Transmission Graphs , author =. 2023 , journal =. doi:10.57717/CGT.V2I1.25 , copyright =

    work page doi:10.57717/cgt.v2i1.25 2023

  65. [65]

    2016 , month = jan, journal =

    Strongly Sublinear Separators and Polynomial Expansion , author =. 2016 , month = jan, journal =

    work page 2016

  66. [66]

    2023 , eprint =

    Faster Matrix Multiplication via Asymmetric Hashing , author =. 2023 , eprint =

    work page 2023

  67. [67]

    2022 , month = apr, journal =

    The Diameter of AT-Free Graphs , author =. 2022 , month = apr, journal =. doi:10.1002/jgt.22754 , urldate =

    work page doi:10.1002/jgt.22754 2022

  68. [68]

    Distance Problems within Helly Graphs and

    Ducoffe, Guillaume , year =. Distance Problems within Helly Graphs and. Theoretical Computer Science , volume =. doi:10.1016/j.tcs.2023.113690 , urldate =

    work page doi:10.1016/j.tcs.2023.113690 2023

  69. [69]

    Graph-Theoretic Concepts in Computer Science , author =

    Beyond Helly Graphs: The Diameter Problem on Absolute Retracts , shorttitle =. Graph-Theoretic Concepts in Computer Science , author =. 2021 , pages =

    work page 2021

  70. [70]

    2020 , month = oct, number =

    Isometric Embeddings in Trees and Their Use in the Diameter Problem , author =. 2020 , month = oct, number =. 2010.15803 , primaryclass =

    work page arXiv 2020

  71. [71]

    17th International Symposium on Parameterized and Exact Computation (IPEC 2022) , author =

    Obstructions to Faster Diameter Computation: Asteroidal Sets , shorttitle =. 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) , author =. 2022 , volume =

    work page 2022

  72. [72]

    Ducoffe, Guillaume , year =. "Propri

    work page

  73. [73]

    30th ACM-SIAM Symposium on Discrete Algorithms (SODA) , author =

    Diameter Computation on. 30th ACM-SIAM Symposium on Discrete Algorithms (SODA) , author =. 2019 , _month = dec, series =

    work page 2019

  74. [74]

    Diameter, Eccentricities and Distance Oracle Computations on

    Ducoffe, Guillaume and Habib, Michel and Viennot, Laurent , year =. Diameter, Eccentricities and Distance Oracle Computations on. SIAM Journal on Computing , volume =

    work page

  75. [75]

    32nd Annual European Symposium on Algorithms (ESA) , author =

    Better Diameter Algorithms for Bounded. 32nd Annual European Symposium on Algorithms (ESA) , author =. 2024 , volume =

    work page 2024

  76. [76]

    2001 , _month = sep, journal =

    Geometry Helps in Bottleneck Matching and Related Problems , author =. 2001 , _month = sep, journal =

    work page 2001

  77. [77]

    1964 , journal =

    Extremal Problems in Graph Theory , author =. 1964 , journal =

    work page 1964

  78. [78]

    New Lower Bounds for

    Erickson, Jeff , year =. New Lower Bounds for. Discrete & Computational Geometry , volume =

    work page

  79. [79]

    2021 , series =

    Truly Subquadratic Exact Distance Oracles with Constant Query Time for Planar Graphs , booktitle =. 2021 , series =

    work page 2021

  80. [80]

    1987 , journal =

    Fast Algorithms for Shortest Paths in Planar Graphs, with Applications , author =. 1987 , journal =

    work page 1987

Showing first 80 references.