Approximate tree decompositions of planar graphs in linear time
type: Item
instance of: scholarly article
title: Approximate tree decompositions of planar graphs in linear time
zbMATH Open document ID: 1348.68296
author: Frank Kammer
author: Torsten Tholey
published in: Theoretical Computer Science
publication date: 2016-08-31T00:00:00Z
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6620940
zbMATH Keywords: (weighted) treewidth
zbMATH Keywords: branchwidth
zbMATH Keywords: rank-width
zbMATH Keywords: planar graph
zbMATH Keywords: linear time
zbMATH Keywords: bidimensionality
MaRDI profile type: Publication
full work available at URL: j.tcs.2016.06.040
OpenAlex ID: W2475293459
cites work: Q5743430
cites work: Graph minors. III. Planar tree-width
cites work: Easy problems for tree-decomposable graphs
cites work: Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
cites work: Graph minors. II. Algorithmic aspects of tree-width
cites work: Complexity of Finding Embeddings in a k-Tree
cites work: Q4036592
cites work: Q4036591
cites work: Graph minors. XIII: The disjoint paths problem
cites work: A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
cites work: Improved Approximation Algorithms for Minimum Weight Vertex Separators
cites work: Approximation algorithms for treewidth
cites work: Q4291429
cites work: Call routing and the ratcatcher
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
cites work: Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
cites work: Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs
cites work: A partial k-arboretum of graphs with bounded treewidth
cites work: Rank-width and tree-width of \(H\)-minor-free graphs
cites work: Rank‐width is less than or equal to branch‐width
cites work: Q4414505
cites work: A note on two problems in connexion with graphs
cites work: Efficient Planarity Testing
DOI: 10.1016/J.TCS.2016.06.040
description: scientific article; zbMATH DE number 6620940