TY - GEN
T1 - Approximating Branchwidth on Parametric Extensions of Planarity
AU - Thilikos, Dimitrios M.
AU - Wiederrecht, Sebastian
N1 - Publisher Copyright:
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.
PY - 2025
Y1 - 2025
N2 - The branchwidth of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated “Ratcatcher”-algorithm of Seymour and Thomas. We investigate an extension of this algorithm to minor-closed graph classes, further than planar graphs, as follows: Let H1 be a graph embeddable in the torus and H2 be a graph embeddable in the projective plane. We prove that every {H1,H2}-minor free graph G contains a subgraph G′ where the difference between the branchwidth of G and the branchwidth of G′ is bounded by some constant, depending only on H1 and H2. Moreover, the graph G′ admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving a constant-additive approximation for branchwidth: For {H1,H2}-minor free graphs, there is a constant c (depending on H1 and H2) and an O(|V(G)|3)-time algorithm that, given a graph G, outputs a value b such that the branchwidth of G is between b and b+c.
AB - The branchwidth of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated “Ratcatcher”-algorithm of Seymour and Thomas. We investigate an extension of this algorithm to minor-closed graph classes, further than planar graphs, as follows: Let H1 be a graph embeddable in the torus and H2 be a graph embeddable in the projective plane. We prove that every {H1,H2}-minor free graph G contains a subgraph G′ where the difference between the branchwidth of G and the branchwidth of G′ is bounded by some constant, depending only on H1 and H2. Moreover, the graph G′ admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving a constant-additive approximation for branchwidth: For {H1,H2}-minor free graphs, there is a constant c (depending on H1 and H2) and an O(|V(G)|3)-time algorithm that, given a graph G, outputs a value b such that the branchwidth of G is between b and b+c.
KW - Approximation algorithm
KW - Branchwidth
KW - Slope
KW - Tangle
KW - Tree decomposition
UR - http://www.scopus.com/inward/record.url?scp=85218467665&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85218467665&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-75409-8_32
DO - 10.1007/978-3-031-75409-8_32
M3 - Conference contribution
AN - SCOPUS:85218467665
SN - 9783031754081
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 460
EP - 474
BT - Graph-Theoretic Concepts in Computer Science - 50th International Workshop, WG 2024, Revised Selected Papers
A2 - Kráľ, Daniel
A2 - Milanič, Martin
PB - Springer Science and Business Media Deutschland GmbH
T2 - 50th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2024
Y2 - 19 June 2024 through 21 June 2024
ER -