Tree-width and large grid minors in planar graphs

zbMATH Open1283.05072MaRDI QIDQ5403052FDOQ5403052

Authors: Alexander Grigoriev 

Publication date: 25 March 2014

Full work available at URL: https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1362/0.html

Recommendations

• scientific article; zbMATH DE number 1262812
• Graph minors. V. Excluding a planar graph
• On planar graphs with large tree-width and small grid minors
• Graph minors. III. Planar tree-width
• Quickly excluding a planar graph

zbMATH Keywords

minorplanar graphtree decompositiongrid graphtree width

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Cited In (14)

• Grid minors in damaged grids
• Linearity of grid minors in treewidth with applications through bidimensionality
• A bound on the treewidth of planar even-hole-free graphs
• A note on planar graphs with large width parameters and small grid-minors
• Large-treewidth graph decompositions and applications
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• 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
• A fast algorithm for the product structure of planar graphs
• On planar graphs with large tree-width and small grid minors
• On the tree-width of planar graphs
• Algebraically grid-like graphs have large tree-width
• Improved bounds on the planar branchwidth with respect to the largest grid minor size

This page was built for publication: Tree-width and large grid minors in planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5403052)