Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2022.19
URN: urn:nbn:de:0030-drops-161797
URL: https://drops.dagstuhl.de/opus/volltexte/2022/16179/
Bose, Prosenjit ; Morin, Pat ; Odak, Saeed
An Optimal Algorithm for Product Structure in Planar Graphs
| pdf-format: |
|
Abstract
The Product Structure Theorem for planar graphs (Dujmović et al. JACM, 67(4):22) states that any planar graph is contained in the strong product of a planar 3-tree, a path, and a 3-cycle. We give a simple linear-time algorithm for finding this decomposition as well as several related decompositions. This improves on the previous O(nlog n) time algorithm (Morin. Algorithmica, 85(5):1544-1558).
BibTeX - Entry
@InProceedings{bose_et_al:LIPIcs.SWAT.2022.19,
author = {Bose, Prosenjit and Morin, Pat and Odak, Saeed},
title = {{An Optimal Algorithm for Product Structure in Planar Graphs}},
booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
pages = {19:1--19:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-236-5},
ISSN = {1868-8969},
year = {2022},
volume = {227},
editor = {Czumaj, Artur and Xin, Qin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16179},
URN = {urn:nbn:de:0030-drops-161797},
doi = {10.4230/LIPIcs.SWAT.2022.19},
annote = {Keywords: Planar graphs, product structure}
}
| Keywords: | Planar graphs, product structure | |
| Seminar: | 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022) | |
| Issue date: | 2022 | |
| Date of publication: | 22.06.2022 |
