An Improved Planar Graph Product Structure Theorem
Abstract:
Dujmović, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every planar graph G there is a graph H with treewidth at most 8 and a path P such that G ⊆ H ⊠ P. We improve this result by replacing "treewidth at most 8" by "simple treewidth at most 6".
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Zeitschriftenaufsatz |
| Publikationsjahr | 2022 |
| Sprache | Englisch |
| Identifikator | ISSN: 1077-8926 KITopen-ID: 1000148527 |
| Erschienen in | The Electronic Journal of Combinatorics |
| Verlag | Electronic Journal of Combinatorics |
| Band | 29 |
| Heft | 2 |
| Seiten | Art.-Nr.: P2.51 |
| Vorab online veröffentlicht am | 17.06.2022 |
| Nachgewiesen in | Web of Science Dimensions Scopus OpenAlex |
| Relationen in KITopen |
Seitenaufrufe: 82
seit 13.07.2022
seit 13.07.2022
Downloads: 87
seit 13.07.2022
seit 13.07.2022