Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.18176 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |