Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2506.12635 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911205301420032 |
|---|---|
| author | Grigoriev, Alexander Kobayashi, Yasuaki Tamaki, Hisao van der Zanden, Tom C. |
| author_facet | Grigoriev, Alexander Kobayashi, Yasuaki Tamaki, Hisao van der Zanden, Tom C. |
| contents | We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithms due to Bouchitt{é} and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12635 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs Grigoriev, Alexander Kobayashi, Yasuaki Tamaki, Hisao van der Zanden, Tom C. Data Structures and Algorithms We develop a new characterization of potential maximal cliques of a triconnected planar graph and, using this characterization, give a polynomial delay algorithm generating all potential maximal cliques of a given triconnected planar graph. Combined with the dynamic programming algorithms due to Bouchitt{é} and Todinca, this algorithm leads to a treewidth algorithm for general planar graphs that runs in time linear in the number of potential maximal cliques and polynomial in the number of vertices. |
| title | A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2506.12635 |