A finite presentation of graphs of treewidth at most three
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866929683829882880 |
|---|---|
| author | Doumane, Amina Humeau, Samuel Pous, Damien |
| author_facet | Doumane, Amina Humeau, Samuel Pous, Damien |
| contents | We provide a finite equational presentation of graphs of treewidth at most three, solving an instanceof an open problem by Courcelle and Engelfriet. We use a syntax generalising series-parallel expressions, denoting graphs with a small interface. Weintroduce appropriate notions of connectivity for such graphs (components, cutvertices, separationpairs). We use those concepts to analyse the structure of graphs of treewidth at most three, showinghow they can be decomposed recursively, first canonically into connected parallel components, andthen non-deterministically. The main difficulty consists in showing that all non-deterministic choicescan be related using only finitely many equational axioms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18176 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A finite presentation of graphs of treewidth at most three Doumane, Amina Humeau, Samuel Pous, Damien Logic in Computer Science We provide a finite equational presentation of graphs of treewidth at most three, solving an instanceof an open problem by Courcelle and Engelfriet. We use a syntax generalising series-parallel expressions, denoting graphs with a small interface. Weintroduce appropriate notions of connectivity for such graphs (components, cutvertices, separationpairs). We use those concepts to analyse the structure of graphs of treewidth at most three, showinghow they can be decomposed recursively, first canonically into connected parallel components, andthen non-deterministically. The main difficulty consists in showing that all non-deterministic choicescan be related using only finitely many equational axioms. |
| title | A finite presentation of graphs of treewidth at most three |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2411.18176 |