Improved bounds on the planar branchwidth with respect to the largest grid minor size
From MaRDI portal
Publication:1934314
DOI10.1007/s00453-012-9627-5zbMath1257.05028OpenAlexW2147929948MaRDI QIDQ1934314
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
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
