Approximate tree decompositions of planar graphs in linear time

DOI10.1016/j.tcs.2016.06.040zbMath1348.68296OpenAlexW2475293459MaRDI QIDQ306256

Torsten Tholey, Frank Kammer

Publication date: 31 August 2016

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

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

zbMATH Keywords

planar graphlinear timerank-width(weighted) treewidthbidimensionalitybranchwidth

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (6)

On Computing the Hamiltonian Index of Graphs ⋮ New analysis and computational study for the planar connected dominating set problem ⋮ Treelength of series-parallel graphs ⋮ On computing the Hamiltonian index of graphs ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Large Independent Sets in Subquartic Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• Rank-width and tree-width of \(H\)-minor-free graphs
• Graph minors. III. Planar tree-width
• Approximation algorithms for treewidth
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
• Graph minors. XIII: The disjoint paths problem
• Easy problems for tree-decomposable graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• Improved Approximation Algorithms for Minimum Weight Vertex Separators
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• Efficient Planarity Testing
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• Rank‐width is less than or equal to branch‐width
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Approximate tree decompositions of planar graphs in linear time