2026-07-26T00:47:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17000 2024-03-06T10:58:56Z ddc:004 open_access

Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs Goetze, Miriam Jungeblut, Paul Ueckerdt, Torsten edge colorings planar graphs cubic graphs generalized factors SPQR-tree It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an n-vertex planar graph, augments this graph in 𝒪(n²) steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized (Anti)factor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Miriam Goetze and Paul Jungeblut and Torsten Ueckerdt 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.62 urn:nbn:de:0030-drops-170007 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.62 eng https://creativecommons.org/licenses/by/4.0/legalcode