Pith. sign in

REVIEW 2 major objections 3 minor 60 references

Graph parameters that are coarsely equivalent to tree-length

T0 review · 2 major / 3 minor · reviewed 2026-08-09 · deepseek-v4-flash

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

Pith's one-line read A graph's tree-length is bounded exactly when eighteen related parameters are bounded.

desk verdict The proofs are mostly solid, but the paper's central claim of multiplicative coarse equivalence is false under its own definition because parameters like adt and bnc vanish on trees while tree-length is 1. read the letter →

arxiv 2502.00951 v1 pith:IJFDZTX5 submitted 2025-02-02 math.CO cs.DS

Feodor F. Dragan This is my paper · ORCID
classification math.COcs.DS MSC 05C1005C62
keywords coarseequivalencetree-lengthtree-decompositionlayeringpartitionbrambleHellyfamilydistance-approximatingtreecyclebridgingproperty
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

Tree-length measures how tree-like a graph is: it is the smallest possible maximum diameter of a bag in a tree-decomposition. The paper's central claim is that tree-length and a family of eighteen graph parameters are coarsely equivalent, meaning each parameter is trapped between a constant multiple of tree-length and a constant multiple of the others for every graph. The new parameters added to this list include the radius of a single disk needed to pierce every bramble, every Helly family of connected subgraphs, or every Helly family of paths, and the smallest distortion with which the graph's own vertex set can be embedded into an unweighted tree. The paper also introduces a cycle bridging constant and shows it sits on the same scale. A sympathetic reader should care because any algorithm, bound, or structural fact that holds for bounded tree-length automatically transfers to every graph with any of these parameters bounded, and several of them are much easier to compute or certify.

What carries the argument

The load-bearing object is the layering partition of a graph with respect to a start vertex, together with its cluster-diameter $\Delta_s(G)$, the largest metric diameter of a cluster in that partition. The paper uses the previously established sandwich $\Delta_s(G)/3 \leq tl(G) \leq \Delta_s(G)+1$ to translate every new or old parameter bound into a tree-length bound, and it repeatedly converts combinatorial witnesses (a bramble, a Helly family, a path avoiding a disk, a cycle failing a locality condition) into two vertices in one cluster, bounding their distance by $\Delta_s(G)$. A second workhorse is the canonical tree built from a layering partition, which shows that a small cluster-diameter yields an additive approximation of graph distances by an unweighted tree on the same vertex set, and conversely Lemma 7 turns a distance-approximating tree into a tree-decomposition via powers of trees, which are chordal graphs.

What would settle it

Take a chordal graph (tree-length 1) with unbounded clique size and compute the bramble interception radius $br(G)$: the theorem predicts $br(G) \leq 1$, so any chordal graph whose brambles require a disk of radius 2 or more would refute the claimed coarse equivalence between $br$ and tree-breadth.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the list $\{tl, tb, itl, itb, \Delta_s, \rho_s, td, ad, adt, bnc, mcw, ph, sh, br, mf, glc, cbc, bgc\}$ forms a single coarse equivalence class: for every graph $G$, any two of these parameters are within small universal constant factors of each other, so boundedness of any one of them is equivalent to bounded tree-length. The new equivalences are stated as sandwich inequalities: for example, $(tl(G)-1)/2 \leq adt(G) \leq 3\,tl(G)$ for distance-approximating trees on the same vertex set, $mcw(G) \leq ph(G) \leq sh(G) \leq br(G) \leq tb(G) \leq tl(G) \leq 6\,mcw(G)+1$ for disk interception of brambles and Helly families, and $\frac{2}{3}(cbc(G)-1) \leq tl(G) \leq 4\,cbc(G)+3$ for the cycle bridging constant. Earlier results on bottleneck constant, McCarty-width, $K_3$-minor fatness, and geodesic loaded cycles are reproved with simpler, more direct arguments and, in several cases, improved constants.

Load-bearing premise

The chain of equivalences rests on previously published inequalities, most crucially that every graph satisfies $\Delta_s(G)/3 \leq tl(G) \leq \Delta_s(G)+1$ for the cluster-diameter of any layering partition, and if those quoted bounds failed, all the new constants would shift, even though the qualitative bounded-versus-bounded picture could survive.

Editorial extensions

If this is right

  • Because a layering partition is computed in linear time, its cluster-diameter gives a fast constant-factor approximation to tree-length and to every parameter on the list.
  • Any structural or algorithmic result proved for bounded tree-length now applies verbatim to graphs with bounded bramble-interception radius, bounded Helly-family interception radius, bounded additive tree distortion, or bounded cycle bridging constant.
  • The embedding result says that bounded tree-length is equivalent to embedding the graph's own vertices into an unweighted tree with small additive distortion and no Steiner points, the strongest form of tree approximation on the list.
  • The bramble and Helly characterizations give a min-max flavor to tree-breadth: a small-radius disk pierces every pairwise-touching connected family exactly when the graph has a tree-decomposition of small breadth.
  • The cycle bridging constant provides a purely local cycle condition that certifies bounded tree-length, generalizing the chordal graph property that every vertex in a cycle has two neighbors that are adjacent.

Reading between the lines

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

  • If the equivalence class is as robust as claimed, one could search for additional parameters that are easier to certify than tree-length: any invariant that is sandwiched between two bounded functions of $tl$ will automatically join the class.
  • The polynomial-time computability of $bnc$ and $mcw$, though with worse constants than the 3-approximation via layering partitions, suggests these parameters could serve as certificates or upper-bound witnesses in algorithms where tree-length itself is NP-hard to compute.
  • The open question whether $br(G) = tb(G)$ could be tested by exhaustively computing both parameters on small graphs; a positive answer would make the bramble-piercing radius an exact, not just coarse, dual of tree-breadth.
  • The cycle bridging and non-locally geodesic constants are defined by local checks; one might try to turn them into polynomial-time certificates of bounded tree-length, though the paper does not claim an algorithm for them.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 3 minor

Summary. The paper studies graph parameters that are claimed to be coarsely equivalent to tree-length. It recasts several known results in a unified layering-partition framework, giving simpler proofs and sometimes improved constants for the bottleneck constant, McCarty-width, K-fat K3-minors, and additive tree embeddings, and it introduces new parameters: bramble and Helly-family interception radii (br, sh, ph), additive distortion to an unweighted tree on the same vertex set (adt), and two cycle bridging constants (cbc, bgc). The main results are explicit two-sided inequalities relating these parameters to tl(G) and tb(G), showing that boundedness of any one parameter is equivalent to bounded tree-length.

Significance. If the framing is corrected, the paper is a useful contribution. It provides a coherent set of explicit inequalities, simplifies and extends known proofs, improves several constants, and proposes new boundedness characterizations that are natural and likely to be useful in algorithmic applications and in further structural work. The paper is mostly self-contained, and the inequalities are stated with explicit constants. The substantive content—the additive inequalities and the resulting boundedness equivalences—appears sound, but the formal claim of multiplicative coarse equivalence is not.

major comments (2)
  1. [Section 1; Theorem 2; Theorem 3; Corollary 4; Proposition 15] The definition of coarse equivalence in Section 1 requires universal constants α, β > 0 with α·q(G) ≤ p(G) ≤ β·q(G) for every graph G. This is incompatible with the paper's own inequalities for parameters that vanish on trees. For the 3-vertex path P3, tl(P3) = 1, while Δs(P3) = ρs(P3) = adt(P3) = bnc(P3) = mcw(P3) = ph(P3) = sh(P3) = glc(P3) = mf(P3) = 0. Hence no positive β can satisfy tl(P3) ≤ β·q(P3) for any of these q. The theorems therefore do not establish 'within constant factors' in the formal sense; they establish boundedness equivalence with additive constants, e.g., Corollary 4 gives (tl−1)/2 ≤ adt(G) ≤ 3·tl(G), Theorem 2 gives mcw(G) ≤ tb(G) ≤ tl(G) ≤ 6·mcw(G)+1, and Proposition 15 gives mcw(G) ≤ ph(G) ≤ sh(G) ≤ br(G) ≤ tb(G). The abstract, introduction, and conclusion should be reworded to state boundedness equivalence, or the definition of coarse equivalence should be modified to allow additive constants; the current wording is mathematically false as written.
  2. [Theorem 4] The displayed chain 'mf(G) ≤ 2·bnc(G)+1 ≤ Δs(G)+1 ≤ 5·mf(G)' is false as stated for arbitrary s. Let G be the 4-cycle with one chord, i.e., vertices 0,1,2,3 and edges 01,12,23,30,02. For s = 1, the layering partition has layer 1 equal to {0,2}, which forms one cluster of diameter 1, so Δ1(G) = 1. The bottleneck constant is bnc(G) = 1: the pair (1,3) has distance 2 with two shortest paths, 1-0-3 and 1-2-3; their middle vertices 0 and 2 are at distance 1, and no radius 0 works. Thus 2·bnc(G)+1 = 3 > 2 = Δ1(G)+1. The cited ingredients (Lemma 1 and Corollary 1) give only bnc ≤ 3/2·Δs, which yields 2·bnc ≤ 3·Δs, not 2·bnc ≤ Δs. This step needs to be repaired or the constants in Theorem 4 changed.
minor comments (3)
  1. [Corollary 5] The proof says 'applying Lemma 5 three times', but Lemma 5 is the balanced clique-separator lemma for chordal graphs; the intended reference appears to be Lemma 8, the distance-approximating tree lemma.
  2. [Section 2.1] There is a typo in the notation 'dG(S1.S2)'; it should be 'dG(S1, S2)'.
  3. [Introduction and Conclusion] The list of parameters in the introduction includes glc(G), but the paper gives no new bounds for glc(G) beyond the quoted Proposition 14 from [9]. The text should clarify which parameters receive new proofs versus which are only cited, to avoid implying that glc is treated here.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new parameters are defined independently and are tied to tree-length via external prior bounds and self-contained lemmas.

full rationale

The paper's derivation chain is not circular. The new parameters (br, sh, ph, adt, cbc, bgc) are defined directly from graph structure, not from tree-length, and each theorem relating them to tl is proved by explicit inequalities. The load-bearing bridge is Proposition 5, quoted from [27]: “Δs(G)/3 ≤ tl(G) ≤ Δs(G) + 1.” This is an external, previously published result independent of the present paper. Other quoted bounds, such as the Berger–Seymour bottleneck and McCarty-width results [9] and Manning's theorem [56], are likewise external. Where the author cites his own earlier work (e.g., Proposition 2 from [21] and Proposition 1 from [35]), the cited results are metric estimates for layering partitions and canonical trees; they do not assume the tree-length conclusion being tested, so they are independent support rather than a self-citation loop. The new Lemmas 1–16 are self-contained and do not presuppose the target equivalences. No parameter is fitted, normalized, or defined in terms of tl, and no 'prediction' is read back from a subset of the data. A non-circular correctness concern should be noted separately: the formal multiplicative definition of coarse equivalence in Section 1 cannot literally hold for parameters that are 0 on trees (e.g., Δs, ρs, adt, bnc, mcw, ph, sh, br) while tl(tree) = 1; the paper's own theorems mostly establish additive inequalities such as (tl−1)/2 ≤ adt(G) ≤ 3·tl(G). That is a mismatch between the stated definition and the proved statements, but it is not a circular derivation and does not raise the circularity score.

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

No data-fitting parameters appear; all constants are fixed integers. The new graph parameters are explicit mathematical definitions rather than postulated entities. The proof backbone is a set of standard theorems and previously published bounds, listed above.

assumptions (6)
  • domain assumption Known bound connecting cluster-diameter of a layering partition to tree-length: Δs(G)/3 ≤ tl(G) ≤ Δs(G)+1.
    Used as the backbone in most proofs, introduced in Section 2.2 as Proposition 5 and invoked in Theorems 1-6.
  • standard math Powers of trees are chordal, so T^{r+1} has a clique-tree.
    Used in Lemma 7 to build a tree-decomposition from a distance k-approximating tree.
  • standard math Every bramble of a graph is intercepted by some bag of every tree-decomposition.
    Used in Proposition 15 to prove br(G) ≤ tb(G), relying on the Seymour-Thomas min-max theorem [58].
  • standard math Chordal graphs have balanced clique separators for arbitrary vertex sets.
    Used in Lemma 6 to prove mcw_k(G) ≤ tb(G), relying on the Gilbert-Rose-Edenbrandt separator theorem [45].
  • standard math Every node-weighted tree has a median whose removal splits the total weight evenly.
    Used in Lemma 4 to construct balanced disk separators from the layering tree.
  • domain assumption Previously published results on quasi-isometry to trees, bottleneck constants, and K-fat K3-minors are correct.
    Used to import bounds such as mf(G) ≤ 2bnc(G)+1 and the equivalence statements from Manning, Kerr, Berger-Seymour, and Georgakopoulos-Papasoglu.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Graph parameters that are coarsely equivalent to tree-length." pith.science (2026). https://pith.science/paper/IJFDZTX5

@misc{pith2026250200951,
  author       = {Pith},
  title        = {Pith review of: Graph parameters that are coarsely equivalent to tree-length},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IJFDZTX5}},
  note         = {Machine review of arXiv:2502.00951}
}
abstract

Two graph parameters are said to be coarsely equivalent if they are within constant factors from each other for every graph $G$. Recently, several graph parameters were shown to be coarsely equivalent to tree-length. Recall that the length of a tree-decomposition ${\cal T}(G)$ of a graph $G$ is the largest diameter of a bag in ${\cal T}(G)$, and the tree-length of $G$ is the minimum of the length, over all tree-decompositions of $G$. We present simpler and sometimes with better bounds proofs for those known in literature results and further extend this list of graph parameters coarsely equivalent to tree-length. Among other new results, we show that the tree-length of a graph $G$ is small if and only if for every bramble ${\cal F}$ (or every Helly family of connected subgraphs ${\cal F}$, or every Helly family of paths ${\cal F}$) of $G$, there is a disk in $G$ with small radius that intercepts all members of ${\cal F}$. Furthermore, the tree-length of a graph $G$ is small if and only if $G$ can be embedded with a small additive distortion to an unweighted tree with the same vertex set as in $G$ (not involving any Steiner points). Additionally, we introduce a new natural "bridging`` property for cycles, which generalizes a known property of cycles in chordal graphs, and show that it also coarsely defines the tree-length.

Figures

Figures reproduced from arXiv: 2502.00951 by the authors.

Figure 1
Figure 1. Layering partition and associated constructs (taken from [1]). A layering tree Γ(G, s) of a graph G with respect to a layering partition LP(G, s) is the graph whose nodes are the clusters of LP(G, s) and where two nodes C = L i j and C ′ = L i ′ j ′ are adjacent in Γ(G, s) if and only if there exist a vertex u ∈ C and a vertex v ∈ C ′ such that uv ∈ E. It was shown in [11] that the graph Γ(G, s) is always a tree and… view at source ↗
Figure 2
Figure 2. Illustrations to the proofs of Lemma 1 and Lemma 2. Proof. Let s be an arbitrary vertex of G and LP(G, s) be the layering partition of G starting at s. Consider vertices x and y from a cluster of LP(G, s) with dG(x, y) = ∆s(G), and let k := dG(s, x) = dG(s, y) and r := bnc(G). Choose also a path Q connecting x and y outside the disk Dk−1(s). Consider arbitrary shortest paths P(s, x) and P(s, y) of G connecting s wit… view at source ↗
Figure 3
Figure 3. Illustrations to the proof of Lemma 3. Lemma 4. For every graph G, every vertex s of G, and every integer k ≥ 3, mcwk(G) ≤ ρs(G). In particular, mcwk(G) ≤ ρ(G) for every graph G and every integer k ≥ 3. Furthermore, for any subset X ⊆ V of vertices of G, a balanced disk separator Dr(u) with r ≤ ∆s(G) can be found in linear time. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 53 canonical work pages

  1. [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

    work page 2016

  2. [2]

    Al-Saidi, Balanced Disk Separators and Hierarchical Tree Decomposition of Real-Life Networks, MS Thesis, Kent State University, 2015

    M. Al-Saidi, Balanced Disk Separators and Hierarchical Tree Decomposition of Real-Life Networks, MS Thesis, Kent State University, 2015. http://rave.ohiolink.edu/etdc/view?acc num=kent1429541936

    work page 2015

  3. [3]

    Agarwala, V

    R. Agarwala, V. Bafna, M. Farach, B. Narayanan, M. Paterson, M. Thorup, On the approx- imability of numerical taxonomy (fitting distances by tree metrics), SIAM J. Comput. 28 (1999), 1073–1085

    work page 1999

  4. [4]

    Albrechtsen, R

    S. Albrechtsen, R. Diestel, A.-K. Elm, E. Fluck, R.W. Jacobs, P. Knappe, P. Wollan, A structural duality for path-decompositions into parts of small radius, arXiv:2307.08497, https://arxiv.org/abs/2307.08497

    arXiv

  5. [5]

    Badoiu, E.D

    M. Badoiu, E.D. Demaine, M.T. Hajiaghayi, A. Sidiropoulos, M. Zadimoghaddam, Ordinal embedding: approximation algorithms and dimensionality reduction, In: Proceedings of the 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2008), Boston, MA, USA, August 25–27. Lecture Notes in Computer Science, vol. 5...

    work page 2008

  6. [6]

    Badoiu, P

    M. Badoiu, P. Indyk, and A. Sidiropoulos, Approximation algorithms for embedding general metrics into trees, SODA’07, pp. 512–521

    work page

  7. [7]

    Belmonte, F.V

    R. Belmonte, F.V. Fomin, P.A. Golovach, M.S. Ramanujan, Metric Dimension of Bounded Tree-length Graphs, SIAM Journal on Discrete Mathematics, 31 (2017), 1217–1243. https://doi.org/10.1137/16M1057383

    doi:10.1137/16m1057383 2017

  8. [8]

    Bendele, D

    O. Bendele, D. Rautenbach, Additive tree O(ρ log n)-spanners from tree breadth ρ, Theoret- ical Computer Science, 914 (2022), 39–46

    work page 2022

Show all 60 references
  1. [9]

    Berger, P

    E. Berger, P. Seymour, Bounded-Diameter Tree-Decompositions, Combinatorica 44, 659–674 (2024). https://doi.org/10.1007/s00493-024-00088-1

    2024 doi

  2. [10]

    Bodlaender, Discovering Treewidth, In: Vojt´ aˇ s, P., Bielikov´ a, M., Charron-Bost, B., S´ ykora, O

    H.L. Bodlaender, Discovering Treewidth, In: Vojt´ aˇ s, P., Bielikov´ a, M., Charron-Bost, B., S´ ykora, O. (eds) SOFSEM 2005: Theory and Practice of Computer Science. SOFSEM 2005. Lecture Notes in Computer Science, vol 3381. Springer, 2005. https://doi.org/10.1007/978- 3-540-...

    2005 doi

  3. [11]

    Brandst¨ adt, V

    A. Brandst¨ adt, V. Chepoi, and F.F. Dragan, Distance approximating trees for chordal and dually chordal graphs, J. Algorithms, 30 (1999), 166–184

    1999

  4. [12]

    Brandst¨ adt, F.F

    A. Brandst¨ adt, F.F. Dragan, Tree-structured graphs, Handbook of Graph Theory, Combi- natorial Optimization, and Algorithms, London, UK: CRC Press, 2016

    2016

  5. [13]

    Brandst¨ adt, F.F

    A. Brandst¨ adt, F.F. Dragan, H.-O. Le, and V.B. Le, Tree Spanners on Chordal Graphs: Complexity and Algorithms, Theoretical Computer Science,310 (2004), 329-354

    2004

  6. [14]

    Brandst¨ adt, V.B

    A. Brandst¨ adt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, Monographs on Discrete Mathematics and Applications, Series Number 3, SIAM, 1999. https://doi.org/10.1137/1.9780898719796

    1999 doi

  7. [15]

    Buneman, A characterization of rigid circuit graphs, Discrete Math

    A. Buneman, A characterization of rigid circuit graphs, Discrete Math. 9 (1974) 205-212

    1974

  8. [16]

    Cai, D.G

    L. Cai, D.G. Corneil, Tree spanners, SIAM J. Discrete. Math.,8 (1995), 359–387

    1995

  9. [17]

    Chalopin, V

    J. Chalopin, V. Chepoi, A. Genevois, H. Hirai, D. Osajda, Helly groups, Geometry and Topology (in print)

  10. [18]

    Chepoi and F.F

    V. Chepoi and F.F. Dragan, A note on distance approximating trees in graphs, Eur. J. Comb., 21 (2000), 761–766

    2000

  11. [19]

    Chepoi, F

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

    2012

  12. [20]

    Chepoi, F.F

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

    2008

  13. [21]

    Chepoi, F.F

    V. Chepoi, F.F. Dragan, I. Newman, Y. Rabinovich, and Y. Vax` es, Constant approxima- tion algorithms for embedding graph metrics into trees and outerplanar graphs, Discrete & Computational Geometry, 47 (2012), 187–214

    2012

  14. [22]

    Chepoi, B

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

    2007

  15. [23]

    Chepoi, B

    V. Chepoi, B. Fichet, ℓ∞-Approximation via subdominants, J. Math. Psychol. 44 (2000), 600–616

    2000

  16. [24]

    Coudert, G

    D. Coudert, G. Ducoffe, and N. Nisse, To Approximate Treewidth, Use Treelength!, SIAM Journal on Discrete Mathematics,30 (2016), 1424-1436

    2016

  17. [25]

    Diestel, M

    R. Diestel, M. M¨ uller, Connected Tree-Width,Combinatorica, 38 (2018), 381–398

    2018

  18. [26]

    Dourisboure, F.F

    Y. Dourisboure, F.F. Dragan, C. Gavoille, C. Yan, Spanners for bounded tree-length graphs, Theor. Comput. Sci.383 (2007), 34–44

    2007

  19. [27]

    Dourisboure, C

    Y. Dourisboure, C. Gavoille, Tree-decompositions with bags of small diameter, Discrete Math- ematics 307(16) (2007), 2008–2029

    2007

  20. [28]

    Dragan, Short Fill-in with Property Π, In Open Problems of Dagstuhl Seminar 11182 ”Exploiting graph structure to cope with hard problems”, A

    F.F. Dragan, Short Fill-in with Property Π, In Open Problems of Dagstuhl Seminar 11182 ”Exploiting graph structure to cope with hard problems”, A. Brandst¨ adt, M.C. Golumbic, P. Heggernes, R. McConnell (Eds.), In Dagstuhl Reports, Volume 1, Issue 5, pp. 29-46, Schloss Dagstuh...

    2011 doi

  21. [29]

    F.F. Dragan, Tree-like Structures in Graphs: a Metric Point of View, 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2013), June 19 - 21, 2013, L¨ ubeck, Germany, Springer, Lecture Notes in Computer Science, 2013

    2013

  22. [30]

    Dragan, M

    F.F. Dragan, M. Abu-Ata, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Theor. Comput. Sci.547 (2014), 1–17

    2014

  23. [31]

    Dragan, H.M

    F.F. Dragan, H.M. Guarnera, Helly-gap of a graph and vertex eccentricities, Theor. Comput. Sci. 867 (2021), 68–84

    2021

  24. [32]

    Dragan, E

    F.F. Dragan, E. K¨ ohler, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, Algorithmica 69 (2014), 884–905

    2014

  25. [33]

    Dragan, E

    F.F. Dragan, E. K¨ ohler, Graph parameters that are coarsely equivalent to path-length, manuscript in preparation, 2024

    2024

  26. [34]

    Dragan, I

    F.F. Dragan, I. Lomonosov, On compact and efficient routing in certain graph classes, Dis- cret. Appl. Math.155 (2007), 1458–1470

    2007

  27. [35]

    Dragan, A

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

    2019

  28. [36]

    Dragan and C

    F.F. Dragan and C. Yan, Distance Approximating Trees: Complexity and Algorithms, In Proceedings of the 6th Conference on Algorithms and Complexity (CIAC’ 2006), Rome, Italy, May 29-31, 2006, Springer, Lecture Notes in Computer Science 3998, pp. 260–271

    2006

  29. [37]

    Dragan, C

    F.F. Dragan, C. Yan, Collective Tree Spanners in Graphs with Bounded Parameters, Algo- rithmica 57 (2010), 22–43. 27

    2010

  30. [38]

    Dragan, C

    F.F. Dragan, C. Yan, I. Lomonosov, Collective tree spanners of graphs, SIAM J. Discret. Math. 20 (2006), 241–260

    2006

  31. [39]

    Ducoffe, S

    G. Ducoffe, S. Legay, N. Nisse, On the Complexity of Computing Tree-breadth, Algorithmica 82 (2020), 1574–1600. https://doi.org/10.1007/s00453-019-00657-7

    2020 doi

  32. [40]

    Furuse, K

    M. Furuse, K. Yamazaki, A revisit of the scheme for computing treewidth and minimum fill-in, Theoretical Computer Science531 (2014) 66–76

    2014

  33. [41]

    Emek and D

    Y. Emek and D. Peleg, Approximating minimum max-stretch spanning trees on unweighted graphs, SIAM J. Comput.,38 (2008), 1761–1781

    2008

  34. [42]

    Gavoille, M

    C. Gavoille, M. Katz, N.A. Katz, C. Paul, D. Peleg, Approximate distance labeling schemes, Ninth Annual European Symposium on Algorithms (ESA),Lecture Notes in Computer Sci- ence, vol. 2161, Springer, Berlin, 2001, pp. 476–488

    2001

  35. [43]

    Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B,16 (1974) 47-56

    F. Gavril, The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B,16 (1974) 47-56

    1974

  36. [44]

    A Georgakopoulos, P Papasoglu, Graph minors and metric spaces, arXiv:2305.07456, 2023

    2023 arXiv

  37. [45]

    Gilbert, D.J

    J.R. Gilbert, D.J. Rose, A. Edenbrandt, A separator theorem for chordal graphs, SIAM J. Algebr. Discrete Methods5 (1984), 306–313

    1984

  38. [46]

    Goldman, Optimal center location in simple networks, Transportation Science, 5 (1971), 212–221

    A.J. Goldman, Optimal center location in simple networks, Transportation Science, 5 (1971), 212–221

    1971

  39. [47]

    M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980

    1980

  40. [48]

    M. Katz, N. A. Katz, D. Peleg, Distance labeling schemes for well-separated graph classes, 17th Annual Symposium on Theoretical Aspects of Computer Science (STACS),Lecture Notes in Computer Science, vol. 1770, Springer, Berlin, 2000, pp. 516–528

    2000

  41. [49]

    Kerr, Tree approximation in quasi-trees, Groups Geom

    A. Kerr, Tree approximation in quasi-trees, Groups Geom. Dyn. 17 (2023), 1193–1233. arXiv:2012.10741

    2023 arXiv

  42. [50]

    Kratsch, H.-O

    D. Kratsch, H.-O. Le, H. M¨ uller, E. Prisner and D. Wagner, Additive tree spanners, SIAM J. Discrete Math.,17 (2003), 332–340

    2003

  43. [51]

    Leitert, Tree-Breadth of Graphs with Variants and Applications, 2017, PhD thesis, Kent State University, Ohio, USA

    A. Leitert, Tree-Breadth of Graphs with Variants and Applications, 2017, PhD thesis, Kent State University, Ohio, USA

    2017

  44. [52]

    Leitert, F.F

    A. Leitert, F.F. Dragan, On Strong Tree-Breadth. In: Combinatorial Optimization and Applications (COCOA 2016), Lecture Notes in Computer Science 10043, Springer, 2016. https://doi.org/10.1007/978-3-319-48749-6 5

    2016 doi

  45. [53]

    Leitert, F.F

    A. Leitert, F.F. Dragan, Parameterized approximation algorithms for some location problems in graphs, Theor. Comput. Sci.755 (2019), 48–64

    2019

  46. [54]

    Lokshtanov, On the complexity of computing tree-length, Discrete Applied Mathematics 158 (2010), 820–827

    D. Lokshtanov, On the complexity of computing tree-length, Discrete Applied Mathematics 158 (2010), 820–827

    2010

  47. [55]

    J. A. Makowsky and U. Rotics, Optimal spanners in partial k-trees, manuscript

  48. [56]

    Manning, Geometry of pseudocharacters, Geom

    J.F. Manning, Geometry of pseudocharacters, Geom. Topol.9 (2005), 1147–1185

    2005

  49. [57]

    Robertson, P.D

    N. Robertson, P.D. Seymour, Graph minors. II. Algorithmic aspects of tree width, J. of Algorithms, 7 (1986) 309-322

    1986

  50. [58]

    Seymour, R

    P.D. Seymour, R. Thomas, Graph searching and a min-max theorem for tree-width, Journal of Combinatorial Theory,Series B, 58 (1993), 22–33, doi:10.1006/jctb.1993.1027

    1993

  51. [59]

    Umezawa, K

    K. Umezawa, K. Yamazaki, Tree-length equals branch-length, Discrete Mathematics 309 (2009), 4656–4660

    2009

  52. [60]

    Walter, Representations of Rigid Cycle Graphs, Ph.D

    J.R. Walter, Representations of Rigid Cycle Graphs, Ph.D. Wayne State Univ., Detroit (1972) 28 Appendix A: Graph parameters considered Notation Name tl(G), itl(G) tree-length, inner tree-length of G tb(G), itb(G) tree-breadth, inner tree-breadth of G stb(G) strong tree-breadth...

    1972

Pith tools

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