Improved bounds on the planar branchwidth with respect to the largest grid minor size

DOI10.1007/s00453-012-9627-5zbMath1257.05028OpenAlexW2147929948MaRDI QIDQ1934314

Hisao Tamaki, Qian-Ping Gu

Publication date: 28 January 2013

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9627-5

zbMATH Keywords

hypergraphgraph minorplanar graphgridbranchwidthbranch-decomposition

Mathematics Subject Classification ID

Hypergraphs (05C65) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items (21)

Four Shorts Stories on Surprising Algorithmic Uses of Treewidth ⋮ A Retrospective on (Meta) Kernelization ⋮ Irrelevant vertices for the planar disjoint paths problem ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Unnamed Item ⋮ A polynomial-time algorithm for outerplanar diameter improvement ⋮ 1-perfectly orientable \(K_4\)-minor-free and outerplanar graphs ⋮ Grid minors in damaged grids ⋮ Faster parameterized algorithms for minor containment ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Succinct certification of monotone circuits ⋮ Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs ⋮ Fast minor testing in planar graphs ⋮ Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Succinct monotone circuit certification: planarity and parameterized complexity ⋮ On tseitin formulas, read-once branching programs and treewidth ⋮ Decomposition of Map Graphs with Applications. ⋮ Bounded-depth Frege complexity of Tseitin formulas for all graphs ⋮ Planar Digraphs ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• Graph minors. III. Planar tree-width
• On the minimum corridor connection problem and other generalized geometric problems
• Treewidth lower bounds with brambles
• Linearity of grid minors in treewidth with applications through bidimensionality
• Graph minors. V. Excluding a planar graph
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Graph minors. XI: Circuits on a surface
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• On planar graphs with large tree-width and small grid minors
• Approximation algorithms for NP-complete problems on planar graphs
• Algorithms – ESA 2005
• Graph Drawing
• Automata, Languages and Programming
• Algorithms - ESA 2003

This page was built for publication: Improved bounds on the planar branchwidth with respect to the largest grid minor size