Pith. sign in

REVIEW 1 major objections 6 minor 85 references

Bow Metrics and Hyperbolicity

T0 review · 1 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A short-path overlap inequality called the (λ,μ)-bow metric forces bounded hyperbolicity in major graph families, with the general case reduced to bipartite graphs.

desk verdict Solid, significant proof of the bow-metric/hyperbolicity conjecture for several major graph classes; the bipartite/line-graph reduction has fixable gaps. read the letter →

arxiv 2411.16548 v1 pith:6S276KFA submitted 2024-11-25 math.CO cs.DMcs.DS

Feodor F. Dragan , Guillaume Ducoffe , Michel Habib , Laurent Viennot This is my paper · ORCID
classification math.COcs.DMcs.DS MSC 05C1205C75
keywords hyperbolicity(λµ)-bowmetricα_i-metricmeshedgraphsweaklymodularHellytrianglesintervalthinness
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper asks whether a purely metric condition on overlapping shortest paths forces a graph to be hyperbolic, meaning its large-scale distances behave like those of a tree. The condition, called a $(\lambda,\mu)$-bow metric, says that if two shortest paths overlap by more than $\lambda$ edges, then the two far endpoints are at least as far apart as the path through the overlap, minus a constant $\mu$. The authors conjecture that every graph satisfying this condition has hyperbolicity bounded in terms of $\lambda$ and $\mu$ alone. They prove the conjecture for meshed graphs, for graphs with convex balls, for modular, median and Helly graphs, and for bipartite graphs when $\lambda=1$, giving explicit bounds such as $\delta \le 2(\lambda+\mu)+1$ for meshed graphs. They also show the general conjecture would follow from proving it for all bipartite graphs, equivalently for line graphs of bipartite graphs.

What carries the argument

The central object is the $(\lambda,\mu)$-bow metric itself, a four-point inequality on shortest-path overlaps. The proof strategy turns this inequality into two structural finiteness properties: metric triangles with bounded side length and intervals with bounded thinness. A metric triangle is a triple of shortest-path intervals that meet only at their endpoints; a quasi-median of three vertices is the metric triangle obtained by cutting back the three intervals until they touch. Once the bow metric bounds the side length of metric triangles and the thinness of intervals—for meshed graphs, for example, the bound is $3\lambda+2\mu+1$ on thinness and $\lambda+2\mu+1$ on triangle side length—known results (Proposition 7 and Proposition 8 in the paper) convert those two bounds into explicit hyperbolicity and slimness constants. A second mechanism is preservation under graph operations: the 1-subdivision of a $(\lambda,\mu)$-bow graph is $(2\lambda+2,2\mu+2)$-bow, and the line graph of a bipartite $(\lambda,\mu)$-bow graph is $(\lambda-1,\mu+2)$-bow, which is what reduces the general conjecture to bipartite graphs and to line graphs of bipartite graphs.

What would settle it

One infinite family of graphs whose hyperbolicity grows without bound while each graph satisfies a $(\lambda,\mu)$-bow metric with fixed $\lambda$ and $\mu$ would refute the conjecture; by the paper's own Remark 1, any such family must have metric triangles of unbounded side length and unbounded interval thinness, so those two quantities are the concrete place to look. A direct check of the line graph of the 1-subdivision for such candidate graphs would also test the reduction step.

Watch

Extended reading notes

Core claim

The paper's central claim is that the $(\lambda,\mu)$-bow metric implies hyperbolicity in graphs, and it establishes the claim for several large families. For meshed graphs, which include weakly modular graphs, median graphs, Helly graphs, chordal graphs, distance-hereditary graphs and basis graphs of matroids, Theorem 4 gives $\delta \le 2(\lambda+\mu)+1$. For graphs with convex balls, Theorem 5 gives $\delta \le \frac{5}{2}\max\{2,\lambda+2\mu+1\}$; for pseudo-modular and Helly graphs, Corollary 8 gives $\delta \le \max\{(\mu+1)/2,\lambda+1\}$; and for modular and median graphs, Corollary 9 gives $\delta \le \max\{\mu/2,\lambda\}$. Bipartite graphs satisfying a $(1,\mu)$-bow metric are shown to be hyperbolic with $\delta \le 3(\mu+1)/2+4$. The general conjecture is reduced to bipartite graphs and to line graphs of bipartite graphs, so settling either of those cases would settle the conjecture for all graphs.

Load-bearing premise

The load-bearing premise is that the unproved general conjecture is true; the paper's route to it depends on a quoted theorem transferring hyperbolicity between a graph and its line graph, so if that transfer fails with the needed constants, the reduction of the conjecture to bipartite graphs collapses.

Editorial extensions

If this is right

  • Every meshed graph satisfying a $(\lambda,\mu)$-bow metric is hyperbolic with $\delta \le 2(\lambda+\mu)+1$, so all weakly modular subclasses (median, Helly, chordal, distance-hereditary) inherit an explicit bound whenever they satisfy the metric.
  • Graphs with convex balls satisfying a bow metric are hyperbolic with $\delta \le \frac{5}{2}\max\{2,\lambda+2\mu+1\}$, and pseudo-modular, modular, and median graphs get sharper constants from Corollaries 8 and 9.
  • Bipartite graphs satisfying a $(1,\mu)$-bow metric are hyperbolic with $\delta \le 3(\mu+1)/2+4$, extending the earlier $\alpha_i$-metric hyperbolicity bound to this bipartite case.
  • The general conjecture is equivalent to proving the same statement for all bipartite graphs or for all line graphs of bipartite graphs; a proof for either class would settle the conjecture for every graph.
  • Since many classical classes—hyperbolic graphs, slim graphs, tree-length-bounded graphs, k-chordal graphs, and AT-free graphs—satisfy bow metrics with small parameters, the hyperbolicity bounds here apply to all of them through the bow-metric hypothesis.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The reduction to line graphs of bipartite graphs makes the conjecture effectively a question about intersection graphs of edges in bipartite graphs; that structural restriction may be the most promising place to search for either a proof or a counterexample.
  • The explicit bounds in the paper are probably not tight; the rectilinear-grid examples used to show sharpness of several propositions suggest constructing meshed bow-metric graphs with hyperbolicity growing linearly in $\lambda+\mu$ to test Theorem 4.
  • Because Euclidean space satisfies the bow condition with $\lambda=\mu=0$ yet has unbounded hyperbolicity, the graph-only conjecture points to integrality of paths as the essential ingredient; one testable extension is whether the result survives for integer-weighted graphs or only for unweighted graphs.
  • If the conjecture is proved, it would unify the scattered hyperbolicity bounds for chordal, distance-hereditary, AT-free, tree-length, and Helly graph classes under one metric hypothesis, and it would automatically give additive distance-approximation algorithms for every bow-metric graph class.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper studies the (λ,μ)-bow metric introduced by Dragan and Ducoffe, which generalizes both α_i-metrics and δ-hyperbolicity. The authors conjecture that, in graphs, a (λ,μ)-bow metric implies hyperbolicity bounded by a function of λ and μ. They prove this conjecture for meshed graphs (Theorem 4, giving δ ≤ 2(λ+μ)+1), for CB-graphs (Theorem 5), for pseudo-modular/Helly graphs (Corollary 8), for modular/median graphs (Corollary 9), and for graphs with bounded metric-triangle side length or bounded interval thinness (Theorem 1). They also show that several named classes, including AT-free graphs, graphs with bounded tree-length, and k-chordal graphs, satisfy bow metrics with small parameters. Finally, in Section 4.5, they reduce the general conjecture to bipartite graphs or to line graphs of bipartite graphs (Lemma 9, Theorem 6, Corollary 11).

Significance. If correct, the paper makes a substantial advance toward unifying α_i-metrics and hyperbolicity. The strongest self-contained result is Theorem 4 for meshed graphs, with an explicit linear bound δ ≤ 2(λ+μ)+1; since meshed graphs include weakly modular graphs, basis graphs of matroids, and many other classical metric graph classes, the scope is large. The intermediate tools, especially Proposition 8 and Corollary 1, are reusable and clean. The reduction of the general conjecture to bipartite graphs and line graphs of bipartite graphs is elegant and gives a clear target for future work. The paper is honest about the open case of bipartite graphs with λ ≥ 2, and no circularity is present: the conjecture is not assumed in the proofs. The main limitations are local proof gaps, the most significant being the incomplete proof of Lemma 9 in Section 4.5.

major comments (1)
  1. [Section 4.5, Lemma 9] The proof of Lemma 9 fixes d_L(e_x,e_y)=λ, but the (λ−1, μ+2)-bow property requires the inequality for every overlap length d ≥ λ; as written, the cases d > λ are not proved. This is load-bearing because Corollary 10 and Theorem 6 rely on Lemma 9. The gap is repairable: if d>λ, let e_y' be the vertex on a shortest e_x-e_y path contained in a shortest e_u-e_y path with d(e_x,e_y')=λ; then (e_u,e_x,e_y',e_v) satisfies the assumptions of the λ-case, and substituting d(e_y',e_v)=d(e_y',e_y)+d(e_y,e_v)=d−λ+d(e_y,e_v) into the λ-case inequality yields exactly d(e_u,e_v) ≥ d(e_u,e_x)+d+d(e_y,e_v)−(μ+2). Please add this argument explicitly.
minor comments (6)
  1. [Section 4.5, Theorem 6] The statement claims an 'if and only if,' but the proof only establishes that bounded hyperbolicity of L(H) implies bounded hyperbolicity of G; the converse is immediate because L(H) itself satisfies a (2λ+1,2μ+4)-bow metric, and it should be stated for completeness.
  2. [Section 4.5, Theorem 6] Please quote the exact inequalities from [44, Theorem 6] and [44, p.194] that transfer hyperbolicity between H and L(H) and between G and H; this would make the O(f(λ,μ)) dependence in the reduction fully transparent.
  3. [Section 3, Proposition 4] The reduction 'without loss of generality, d(v,w)=2' is valid but should be spelled out; one applies the d=2 case to the quadruple (u,v,v',x), where v' is the vertex at distance 2 from v on the v-w path, and uses d(v',x)=d(v,w)−2+d(w,x).
  4. [Section 3, Proposition 6] The step 'we may assume ... this cycle C is simple' needs a justification; as written, a closed walk formed by four shortest paths need not contain a simple cycle with the stated metric properties, and the subsequent chord argument depends on simplicity.
  5. [Section 4.2, Lemma 4] In the definition of ℓ, the equality d(x',y')=d(x',w') should read d(x',y')=d(y',w').
  6. [Theorem 6] 'A graphs G' should be 'A graph G'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the paper's hyperbolicity bounds are derived from the bow-metric hypothesis plus structural hypotheses, not assumed by construction.

full rationale

The paper's positive results are not circular. Theorem 4 for meshed graphs is reached by first bounding metric-triangle side lengths (Lemma 4) and interval thinness (Corollary 5) from the bow-metric hypothesis, and then applying the paper's own Corollary 1, which converts those two bounds into a hyperbolicity bound. This is a direct inequality chain, not a restatement of the target conclusion. The definitions and Proposition 2 are inherited from the authors' earlier work [51], but they are prior mathematical statements used as lemmas, not assumptions equivalent to the conjecture under test. The meshed, CB-graph, and modular/Helly results are derived in this paper from the stated hypotheses and do not depend on the conjecture. The Section 4.5 reduction to line graphs of bipartite graphs is the least formally complete step: Lemma 9 is written for overlap exactly d_L(e_x,e_y)=lambda, and the constants imported from [44] are quoted without proof. However, that is a correctness and rigor concern about an external transfer theorem, not circularity: the claimed implication is not obtained by defining the target quantity into the hypothesis. There is no fitted parameter renamed as a prediction and no self-citation chain that forces the theorem. Score 1 reflects minor self-citation in the reduction, not actual circularity.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The ledger is clean: no free parameters, no invented entities. The mathematical inputs are the standard apparatus of metric graph theory (quasi-medians, intervals, thinness) and several published theorems that the paper cites rather than reproves.

assumptions (5)
  • domain assumption Every graph considered is finite, undirected, unweighted, simple and connected (Section 2).
    The bow metric and hyperbolicity are defined for such graphs; the results do not extend automatically to infinite or weighted graphs.
  • standard math Every triple of vertices admits a quasi-median (cited to [10]).
    Used in Proposition 8, Lemmas 4, 7, 8 and elsewhere to decompose distances through metric triangles.
  • standard math Every delta-hyperbolic graph satisfies the (delta,2delta)-bow metric (Proposition 2, from [51]).
    Provides the forward direction between hyperbolicity and bow metric; the paper cites the prior proof rather than reproving it.
  • standard math If intervals are p-thin and metric triangle sides are at most q, then slimness and hyperbolicity are bounded (Proposition 7, from [38]).
    This external theorem turns the new thinness bounds from Proposition 9 and Lemma 4 into hyperbolicity bounds.
  • standard math Papasoglu's theorem: hyperbolicity is at most doubly exponential in the interval thinness of the 1-subdivision (Theorem 2, from [76]).
    Used to reduce the general conjecture to bounded interval thinness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bow Metrics and Hyperbolicity." pith.science (2026). https://pith.science/paper/6S276KFA

@misc{pith2026241116548,
  author       = {Pith},
  title        = {Pith review of: Bow Metrics and Hyperbolicity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6S276KFA}},
  note         = {Machine review of arXiv:2411.16548}
}
abstract

A ($\lambda,\mu$)-bow metric was defined in (Dragan & Ducoffe, 2023) as a far reaching generalization of an $\alpha_i$-metric (which is equivalent to a ($0,i$)-bow metric). A graph $G=(V,E)$ is said to satisfy ($\lambda,\mu$)-bow metric if for every four vertices $u,v,w,x$ of $G$ the following holds: if two shortest paths $P(u,w)$ and $P(v,x)$ share a common shortest subpath $P(v,w)$ of length more than $\lambda$ (that is, they overlap by more than $\lambda$), then the distance between $u$ and $x$ is at least $d_G(u,v)+d_G(v,w)+d_G(w,x)-\mu$. ($\lambda,\mu$)-Bow metric can also be considered for all geodesic metric spaces. It was shown by Dragan & Ducoffe that every $\delta$-hyperbolic graph (in fact, every $\delta$-hyperbolic geodesic metric space) satisfies ($\delta, 2\delta$)-bow metric. Thus, ($\lambda,\mu$)-bow metric is a common generalization of hyperbolicity and of $\alpha_i$-metric. In this paper, we investigate an intriguing question whether ($\lambda,\mu$)-bow metric implies hyperbolicity in graphs. Note that, this is not the case for general geodesic metric spaces as Euclidean spaces satisfy ($0,0$)-bow metric whereas they have unbounded hyperbolicity. We conjecture that, in graphs, ($\lambda,\mu$)-bow metric indeed implies hyperbolicity and show that our conjecture is true for several large families of graphs.

Figures

Figures reproduced from arXiv: 2411.16548 by the authors.

Figure 1
Figure 1. An illustration to the proof of Proposition 8 . [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. An illustration to the proof of Proposition 9. [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. An illustration to the proof of Theorem 3. [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: An illustration to the proof of Lemma 4. [PITH_FULL_IMAGE:figures/full_fig_p015_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

85 extracted references · 70 canonical work pages

  1. [51]

    Dragan, G

    F.F. Dragan, G. Ducoffe, αi-Metric Graphs: Hyperbolicity, manuscript, 2023

    work page 2023

  2. [44]

    Coudert, G

    D. Coudert, G. Ducoffe, On the hyperbolicity of bipartite graphs and intersection graphs, Discrete Applied Mathematics 214 (2016), 187-195

    work page 2016

  3. [1]

    Abu-Ata, F.F

    M. Abu-Ata, F.F. Dragan. Metric tree-like structures in real-world networks: an empirical study, Networks 67(1) (2016), 49-68. 19

    2016

  4. [2]

    Albert, B

    R. Albert, B. DasGupta, N. Mobasheri. Topological implications of negative curvature for biological and social networks, Physical Review E 89(3) (2014), 032811

    2014

  5. [3]

    Alonso, T

    J.M. Alonso, T. Brady, D. Cooper, V. Ferlini, M. Lustig, M. Mihalik, M. Shapiro, H. Short, Notes on word hyperbolic groups, Group Theory from a Geometrical Viewpoint, ICTP Trieste 1990 (E. Ghys, A. Haefliger, and A. Verjovsky, eds.), World Scientific, 1991, pp. 3–63

    1990

  6. [4]

    Bandelt, Retracts of hypercubes, J

    H.-J. Bandelt, Retracts of hypercubes, J. Graph Th. 8 (1984), 501–510

    1984

  7. [5]

    Bandelt, J

    H.-J. Bandelt, J. Hedl ´ ıkov´ a, Median algebras,Discr. Math. 45 (1983), 1–30

    1983

  8. [6]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, A Helly theorem in weakly modular space, Discr. Math. 126 (1996), 25–39

    work page 1996

Show all 85 references
  1. [7]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, Graphs with connected medians, SIAM J. Discr. Math. 15 (2002), 268–282

    2002

  2. [8]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, 1-Hyperbolic graphs, SIAM J. Discr. Math. 16 (2003), 323–334

    2003

  3. [9]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, Decomposition and l1-embedding of weakly median graphs, Europ. J. Combin. 21 (2000), 701–714

    2000

  4. [10]

    Bandelt, V

    H.-J. Bandelt, V. Chepoi, Metric graph theory and geometry: a survey, Surveys on discrete and com- putational geometry, Contemp. Math. , vol. 453, Amer. Math. Soc., Providence, RI, 2008, pp. 49–86, DOI 10.1090/conm/453/08795

    2008 doi

  5. [11]

    Bandelt, H.M

    H.-J. Bandelt, H.M. Mulder, Pseudo-modular graphs, Discr. Math. 62 (1986), 245–260

    1986

  6. [12]

    Bandelt, H.M

    H.-J. Bandelt, H.M. Mulder, Cartesian factorization of interval-regular graphs having no long isometric odd cycles, in Graph Theory, Combinatorics, and Applications, vol. 1, Y. Alavi, G. Chartrand, O.R. Oellermann, A.J. Schwenk (eds.), Wiley, New York, 1991, pp. 55–75

    1991

  7. [13]

    Bandelt, H.M

    H.-J. Bandelt, H.M. Mulder, Distance-hereditary graphs, J. Combin. Th. Ser. B 41 (1986), 182–208

    1986

  8. [14]

    Bandelt, H.M

    H.-J. Bandelt, H.M. Mulder, V. Soltan, Weak Cartesian factorization with icosahedra, 5-wheels, and subhyperoctahedra as factors (submitted)

  9. [15]

    Bandelt, E

    H.-J. Bandelt, E. Pesch, Dismantling absolute retracts of reflexive graphs, Eur. J. Comb., 10 (1989), 211–220

    1989

  10. [16]

    Bandelt, E

    H.-J. Bandelt, E. Prisner, Clique graphs and Helly graphs, Journal of Combinatorial Theory , Series B, 51 (1991), 34– 45

    1991

  11. [17]

    Bandelt, M

    H.-J. Bandelt, M. van de Vel, E. Verheul, Modular interval spaces, Math. Nachr. 163 (1993), 177–201

    1993

  12. [18]

    Bondy, U.S.R

    J.A. Bondy, U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, 244 (2008)

    2008

  13. [19]

    Bermudo, W

    S. Bermudo, W. Carballosa, J. M. Rodr ´ ıguez, J. M. Sigarreta, On the hyperbolicity of edge- chordal and path-chordal graphs. Filomat, 30(2016), 2599–2607

    2016

  14. [20]

    Borassi, A

    M. Borassi, A. Chessa, G. Caldarelli. Hyperbolicity measures democracy in real-world networks, Phys- ical Review E 92(3) (2015), 032812

    2015

  15. [21]

    Brandst¨ adt, F.F

    A. Brandst¨ adt, F.F. Dragan, V.D. Chepoi, V.I. Voloshin, Dually chordal graphs, SIAM J. Discrete Math. 11 (1998), 437–455

    1998

  16. [22]

    Brinkmann, J

    G. Brinkmann, J. Koolen, V. Moulton, On the hyperbolicity of chordal graphs, Annals of Combina- torics, 5(2001), 61–69. URL https://ueaeprints.uea.ac.uk/21813/

    2001

  17. [23]

    Cameron, Dual polar spaces, Geom

    P. Cameron, Dual polar spaces, Geom. Dedicata 12 (1982), 75–85. 20

    1982

  18. [24]

    Chalopin, M

    J. Chalopin, M. Changat, V. Chepoi, J. Jacob. First-order logic axiomatization of metric graph theory, arXiv:2203.01070, 2022

    2022 arXiv

  19. [25]

    Chalopin, V

    J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe, A. Mohammed, Y. Vax` es, Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs, Discret. Comput. Geom. 65(2021), 856–892

    2021

  20. [26]

    Chalopin, V

    J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe, A. Mohammed, Y. Vax` es, Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs, Discret. Comput. Geom. , 65 (2021), 856–892. https://doi.org/10.1007/s00454-019-00107-9

    2021 doi

  21. [27]

    Chalopin, V

    J. Chalopin, V. Chepoi, F.F. Dragan, G. Ducoffe, Y. Vax` es,λ-generalized Helly graphs, in preparation, 2023

    2023

  22. [28]

    Chalopin, V

    J. Chalopin, V. Chepoi, U. Giocanti, Graphs with convex balls, Geom. Dedicata (2023) https://doi.org/10.21203/rs.3.rs-2293810/v1

    2023 doi

  23. [29]

    Chalopin, V

    J. Chalopin, V. Chepoi, H. Hirai, D. Osajda, Weakly modular graphs and nonpositive curvature, Memoirs of American Mathematical Society, 268 (2020), no 1309, 159 pp

    2020

  24. [30]

    Chastand, Retracts of infinite Hamming graphs, J

    M. Chastand, Retracts of infinite Hamming graphs, J. Combin. Th. Ser. B 71 (1997), 54–66

    1997

  25. [31]

    Chastand, Fiber-complemented graphs I: structure and invariant subgraphs, Discr

    M. Chastand, Fiber-complemented graphs I: structure and invariant subgraphs, Discr. Math. 226 (2001), 107–141

    2001

  26. [32]

    Chepoi, Some properties of d–convexity in triangulated graphs, Mathematical Research, 87 (1986), Chisinau Stiinta, pp

    V. Chepoi, Some properties of d–convexity in triangulated graphs, Mathematical Research, 87 (1986), Chisinau Stiinta, pp. 164–177 (in Russian)

    1986

  27. [33]

    Chepoi, Centers of triangulated graphs, Math

    V. Chepoi, Centers of triangulated graphs, Math. Notes 43 (1988), 143–151

    1988

  28. [34]

    Chepoi, Classifying graphs by metric triangles, Metody Diskretnogo Analiza 49 (1989), 75–93 (Russian)

    V. Chepoi, Classifying graphs by metric triangles, Metody Diskretnogo Analiza 49 (1989), 75–93 (Russian)

    1989

  29. [35]

    Chepoi, Basis graphs of even delta-matroids, J

    V. Chepoi, Basis graphs of even delta-matroids, J. Combin. Th. Ser. B. 97 (2007), 175–192

    2007

  30. [36]

    Chepoi, Separation axiom S3 for geodesic convexity in graphs, arXiv preprint arXiv:2405.07512 (2024)

    V. Chepoi, Separation axiom S3 for geodesic convexity in graphs, arXiv preprint arXiv:2405.07512 (2024)

    2024 arXiv

  31. [37]

    Chepoi, F.F

    V. Chepoi, F.F. Dragan, Finding a central vertex in HHD-free graphs, Discrete Applied Mathematics 131 (2003), 93-111

    2003

  32. [38]

    Chepoi, F.F

    V.D. Chepoi, F.F. Dragan, B. Estellon, M. Habib, Y. Vax` es, Diameters, centers, and approximating trees of δ-hyperbolic geodesic spaces and graphs, Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG 2008), June 9-11, 2008, College Park, Maryland, USA...

    2008

  33. [39]

    Chepoi, F.F

    V. Chepoi, F.F. Dragan, B. Estellon, M. Habib, Y. Vax´ es, Y. Xiang. Additive spanners and distance and routing labeling schemes for hyperbolic graphs, Algorithmica 62 (2012), 713-732

    2012

  34. [40]

    Chepoi, F.F

    V. Chepoi, F.F. Dragan, M. Habib, Y. Vax` es, H. Alrasheed, Fast approximation of eccentricities and distances in hyperbolic graphs, Journal of Graph Algorithms and Applications , 23(2019), 393–433

    2019

  35. [41]

    Chepoi, F.F

    V. Chepoi, F.F. Dragan, Y. Vax` es, Core congestion is inherent in hyperbolic networks, InSODA 2017, pages 2264–2279

    2017

  36. [42]

    Chepoi, B

    V. Chepoi, B. Estellon, Packing and covering δ-hyperbolic spaces by balls, In APPROX-RANDOM 2007 pp. 59–73

    2007

  37. [43]

    Chung, R.L

    F.R.K. Chung, R.L. Graham, M.E. Saks, A dynamic location problem for graphs, Combinatorica 9 (1989), 111–132. 21

    1989

  38. [45]

    Coudert, G

    D. Coudert, G. Ducoffe. Recognition of C4-free and 1/2-hyperbolic graphs, SIAM Journal on Discrete Mathematics 28(3) (2014), 1601-1617

    2014

  39. [46]

    Diestel, M

    R. Diestel, M. M¨ uller, Connected tree-width,Combinatorica, 38(2014), 1–18

    2014

  40. [47]

    Dragan, Centers of graphs and the Helly property (in russian), PhD thesis, Moldova State University, 1989

    F.F. Dragan, Centers of graphs and the Helly property (in russian), PhD thesis, Moldova State University, 1989

    1989

  41. [48]

    F.F. Dragan, Conditions for coincidence of local and global minima for eccentricity function on graphs and the Helly property, Studies in Applied Mathematics and Information Science , pages 49–56, 1990 (in Russian)

    1990

  42. [49]

    Dragan, HT-graphs: centers, connected r-domination and Steiner trees, Comput

    F.F. Dragan, HT-graphs: centers, connected r-domination and Steiner trees, Comput. Sci. J. of Moldova (Kishinev), 1993, Vol.1, N 2, 64–83

    1993

  43. [50]

    Dragan, G

    F.F. Dragan, G. Ducoffe, αi-Metric Graphs: Radius, Diameter and all Eccentricities. Algorithmica 86 (2024), 2092–2129

    2024

  44. [52]

    Dragan, H.M

    F.F. Dragan, H.M. Guarnera, Obstructions to a small hyperbolicity in Helly graphs, Discret. Math. 342(2019), 326–338

    2019

  45. [53]

    Dragan, H.M

    F.F. Dragan, H.M. Guarnera, Helly-gap of a graph and vertex eccentricities, in Theoretical Computer Science, vol. 867, 2021, pp. 68-84

    2021

  46. [54]

    Dragan, E

    F.F. Dragan, E. K¨ ohler, H. Alrasheed, Eccentricity Approximating Trees, Discrete Applied Mathe- matics, 232 (2017), 142–156

    2017

  47. [55]

    Dragan, A

    F.F. Dragan, A. Mohammed, Slimness of graphs, Discret. Math. Theor. Comput. Sci. 21(3) (2019)

    2019

  48. [56]

    Dragan, Ch.F

    F.F. Dragan, Ch.F. Prisacaru, V.D. Chepoi, Location problems in graphs and the Helly property, Discrete Math. (Moscow), 1992, Vol.4, N 4, 67–73 (in Russian)

    1992

  49. [57]

    Dourisboure, C

    Y. Dourisboure, C. Gavoille, Tree-decompositions with bags of small diameter, Discr. Math. 307 (2007) 208–229

    2007

  50. [58]

    Edwards, W.S

    K. Edwards, W.S. Kennedy, I. Saniee, Fast Approximation Algorithms for p-Centers in Large δ- Hyperbolic Graphs, Algorithmica 80 (2018), 3889–3907. https://doi.org/10.1007/s00453-018-0425-6

    2018 doi

  51. [59]

    Eppstein, Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition, In SODA’ 2007

    D. Eppstein, Squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition, In SODA’ 2007

    2007

  52. [60]

    Farber, R.E

    M. Farber, R.E. Jamison, On local convexity in graphs, Discr. Math. 66 (1987), 231–247

    1987

  53. [61]

    Gavoille, O

    C. Gavoille, O. Ly, Distance labeling in hyperbolic graphs, In ISAAC 2005 pp. 171–179

    2005

  54. [62]

    Ghys and P

    E. Ghys and P. de la Harpe eds., Les groupes hyperboliques d’apr` es M. Gromov, Progress in Mathe- matics Vol. 83, Birkh¨ auser (1990)

    1990

  55. [63]

    Gromov, Hyperbolic Groups, pages 75–263

    M. Gromov, Hyperbolic Groups, pages 75–263. Springer, New York, NY, 1987

    1987

  56. [64]

    P. Hell, I. Rival, Absolute retracts and varieties of reflexive graphs, Canad. J. Math. , 39 (1987), 544–567. doi: 10.4153/CJM-1987-025-1

    1987 doi

  57. [65]

    Howorka, A characterization of distance-hereditary graphs, Quart

    E. Howorka, A characterization of distance-hereditary graphs, Quart. J. Math. Oxford Ser. 2, 28 (1977), 417–420. 22

    1977

  58. [66]

    Howorka, On metric properties of certain clique graphs, Journal of Combinatorial Theory, Series B 27(1) (1979), 67–74

    E. Howorka, On metric properties of certain clique graphs, Journal of Combinatorial Theory, Series B 27(1) (1979), 67–74

    1979

  59. [67]

    Isbell, Median algebra, Trans

    J.R. Isbell, Median algebra, Trans. Amer. Math. Soc. 260 (1980), 319–362

    1980

  60. [68]

    Jonckheere, P

    E. Jonckheere, P. Lohsoonthorn. Geometry of network security, inProceedings of the American Control Conference, IEEE, Vol. 2 (2004), pp. 976-981

    2004

  61. [69]

    Krauthgamer, J.R

    R. Krauthgamer, J.R. Lee, Algorithms on negatively curved spaces, In FOCS 2006

    2006

  62. [70]

    W. S. Kennedy, I. Saniee, O. Narayan. On the hyperbolicity of large-scale networks and its estimation, in IEEE International Conference on Big Data (Big Data), IEEE (2016), pp. 3344-3351

    2016

  63. [71]

    Koolen, V

    J.H. Koolen, V. Moulton. Hyperbolic bridged graphs, European Journal of Combinatorics 23(6) (2002), 683-699

    2002

  64. [72]

    Maurer, Matroid basis graphs I, J

    S.B. Maurer, Matroid basis graphs I, J. Combin. Th. Ser. B 14 (1973), 216–240; II, J. Combin. Th. Ser. B 15 (1973), 121–145

    1973

  65. [73]

    de Montgolfier, M

    F. de Montgolfier, M. Soto, L. Viennot, Treewidth and Hyperbolicity of the Internet. NCA 2011: 25–32

    2011

  66. [74]

    Mulder, The Interval Function of a Graph, Math

    H.M. Mulder, The Interval Function of a Graph, Math. Centre Tracts 132 (Amsterdam), 1980

    1980

  67. [75]

    Nowakowski, I

    R. Nowakowski, I. Rival, The smallest graph variety containing all paths, Discrete Mathematics, 43 (1983), 223 – 234

    1983

  68. [76]

    Papasoglu, Strongly geodesically automatic groups are hyperbolic, Inventiones Math

    P. Papasoglu, Strongly geodesically automatic groups are hyperbolic, Inventiones Math. 121 (1995), 323–334

    1995

  69. [77]

    Quilliot, On the Helly property working as a compactness criterion on graphs, Journal of Combi- natorial Theory, Series A, 40 (1985), 186 – 193

    A. Quilliot, On the Helly property working as a compactness criterion on graphs, Journal of Combi- natorial Theory, Series A, 40 (1985), 186 – 193

    1985

  70. [78]

    Shavitt, T

    Y. Shavitt, T. Tankel, On internet embedding in hyperbolic spaces for overlay construction and distance estimation, In INFOCOM 2004

    2004

  71. [79]

    Soltan, V.D

    V.P. Soltan, V.D. Chepoi, Conditions for invariance of set diameters under d-convexification in a graph, Cybernetics 19 (1983), 750–756 (Russian, English transl.)

    1983

  72. [80]

    Soto, Quelques propr ´ ıet´ es topologiques des graphes et applications ` a Internet et aux r´ eseaux, PhD thesis, Universit´ e Paris Diderot, 2011

    M. Soto, Quelques propr ´ ıet´ es topologiques des graphes et applications ` a Internet et aux r´ eseaux, PhD thesis, Universit´ e Paris Diderot, 2011

    2011

  73. [81]

    Verbeek, S

    K. Verbeek, S. Suri, Metric embedding, hyperbolic space, and social networks, Computational Geom- etry, 59 (2016), 1–12

    2016

  74. [82]

    van de Vel, Theory of Convex Structures, Elsevier Science Publishers, Amsterdam, 1993

    M. van de Vel, Theory of Convex Structures, Elsevier Science Publishers, Amsterdam, 1993

    1993

  75. [83]

    Wilkeit, The retracts of Hamming graphs, Discr

    E. Wilkeit, The retracts of Hamming graphs, Discr. Math. 102 (1992), 197–218

    1992

  76. [84]

    Yushmanov, V

    S.V. Yushmanov, V. Chepoi, A general method of investigation of metric graph properties related to the eccentricity, in Mathematical Problems in Cybernetics , vol. 3, Nauka, Moscow, 1991, pp. 217–232 (Russian)

    1991

  77. [85]

    Y. Wu, C. Zhang, Hyperbolicity and chordality of a graph, Electr. J. Comb., 18(1):Paper #P43, 2011. 23

    2011

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.