Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time

DOI10.1016/j.tcs.2010.07.017zbMath1217.68246OpenAlexW2059590924MaRDI QIDQ553343

Hisao Tamaki, Qian-Ping Gu

Publication date: 27 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.07.017

zbMATH Keywords

graph algorithmsgraph minorsbranch-decompositions

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Approximate tree decompositions of planar graphs in linear time ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Improved bounds on the planar branchwidth with respect to the largest grid minor size ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple linear algorithm for the edge-disjoint \((s, t)\)-paths problem in undirected planar graphs
• Approximation algorithms for treewidth
• Treewidth lower bounds with brambles
• Graph minors. I. Excluding a forest
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• Computing the branchwidth of interval graphs
• Graph minors. XIII: The disjoint paths problem
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time
• Easy problems for tree-decomposable graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Constant-Factor Approximations of Branch-Decomposition and Largest Grid Minor of Planar Graphs in O(n 1 + ε ) Time
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Constructive linear time algorithms for branchwidth
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms - ESA 2003