Graph parameters that are coarsely equivalent to tree-length
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929695218466816 |
|---|---|
| author | Dragan, Feodor F. |
| author_facet | Dragan, Feodor F. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00951 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Graph parameters that are coarsely equivalent to tree-length Dragan, Feodor F. Combinatorics Data Structures and Algorithms 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. |
| title | Graph parameters that are coarsely equivalent to tree-length |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.00951 |