A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916985710837760 |
|---|---|
| author | Caoduro, Marco Evans, Will Gaede, Tao |
| author_facet | Caoduro, Marco Evans, Will Gaede, Tao |
| contents | The boxicity of a graph $G$ is the minimum dimension $d$ that admits a representation of $G$ as the intersection graph of a family of axis-parallel boxes in $\mathbb{R}^d$. Computing boxicity is an NP-hard problem, and there are few known graph classes for which it can be computed in polynomial time. One such class is the class of block graphs. A block graph is a graph in which every maximal $2$-connected component is a clique. Since block graphs are known to have boxicity at most two, computing their boxicity amounts to the linear-time interval graph recognition problem. On the other hand, complements of block graphs have unbounded boxicity, yet we show that there is also a polynomial algorithm that computes the boxicity of complements of block graphs. An adaptation of our approach yields a polynomial algorithm for computing the threshold dimension of the complements of block graphs, which for general graphs is an NP-hard problem. Our method suggests a general technique that may show the tractability of similar problems on block-restricted graph classes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02199 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs Caoduro, Marco Evans, Will Gaede, Tao Combinatorics 05C62 (primary) 05C10, 05C85 (secondary) The boxicity of a graph $G$ is the minimum dimension $d$ that admits a representation of $G$ as the intersection graph of a family of axis-parallel boxes in $\mathbb{R}^d$. Computing boxicity is an NP-hard problem, and there are few known graph classes for which it can be computed in polynomial time. One such class is the class of block graphs. A block graph is a graph in which every maximal $2$-connected component is a clique. Since block graphs are known to have boxicity at most two, computing their boxicity amounts to the linear-time interval graph recognition problem. On the other hand, complements of block graphs have unbounded boxicity, yet we show that there is also a polynomial algorithm that computes the boxicity of complements of block graphs. An adaptation of our approach yields a polynomial algorithm for computing the threshold dimension of the complements of block graphs, which for general graphs is an NP-hard problem. Our method suggests a general technique that may show the tractability of similar problems on block-restricted graph classes. |
| title | A polynomial algorithm to compute the boxicity and threshold dimension of complements of block graphs |
| topic | Combinatorics 05C62 (primary) 05C10, 05C85 (secondary) |
| url | https://arxiv.org/abs/2510.02199 |