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 | Forschungsbericht/Preprint |
| Publikationsdatum | 31.07.2021 |
| Sprache | Englisch |
| Identifikator | KITopen-ID: 1000148528 |
| Nachgewiesen in | arXiv Dimensions |
| Relationen in KITopen |