Improved bounds on the planar branchwidth with respect to the largest grid minor size
type: Item
instance of: scholarly article
title: Improved bounds on the planar branchwidth with respect to the largest grid minor size
zbMATH Open document ID: 1257.05028
author: Hisao Tamaki
author: Qian-Ping Gu
published in: Algorithmica
publication date: 2013-01-28T00:00:00Z
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 6131861
zbMATH Keywords: graph minor
zbMATH Keywords: grid
zbMATH Keywords: branchwidth
zbMATH Keywords: branch-decomposition
zbMATH Keywords: planar graph
zbMATH Keywords: hypergraph
MaRDI profile type: Publication
full work available at URL: s00453-012-9627-5
OpenAlex ID: W2147929948
cites work: Approximation algorithms for NP-complete problems on planar graphs
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Treewidth lower bounds with brambles
cites work: On the minimum corridor connection problem and other generalized geometric problems
cites work: Graph Drawing
cites work: Linearity of grid minors in treewidth with applications through bidimensionality
cites work: Algorithms – ESA 2005
cites work: Q3579494
cites work: Q5403052
cites work: On planar graphs with large tree-width and small grid minors
cites work: Automata, Languages and Programming
cites work: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
cites work: Graph minors. III. Planar tree-width
cites work: Graph minors. V. Excluding a planar graph
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Graph minors. XI: Circuits on a surface
cites work: Quickly excluding a planar graph
cites work: Call routing and the ratcatcher
cites work: Algorithms - ESA 2003
DOI: 10.1007/S00453-012-9627-5
Recommended article: Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
Recommended article: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
Recommended article: Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
Recommended article: Q5403052
Recommended article: On planar graphs with large tree-width and small grid minors
Recommended article: Linearity of grid minors in treewidth with applications through bidimensionality
Recommended article: Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs
Recommended article: A note on planar graphs with large width parameters and small grid-minors
Recommended article: Excluded Grid Minors and Efficient Polynomial-Time Approximation Schemes
Recommended article: A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth
description: scientific article; zbMATH DE number 6131861