Tree-width and large grid minors in planar graphs

MaRDI QIDQ5403052zbMATH OpenFDO

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

zbMATH Keywords

grid graphminorplanar graphtree decompositiontree width

Mathematics Subject Classification ID

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

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

Cited in

(15)

• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• 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
• Grid minors in damaged grids
• scientific article; zbMATH DE number 1262812 (Why is no real title available?)
• A note on planar graphs with large width parameters and small grid-minors
• Large-treewidth graph decompositions and applications
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• Algebraically grid-like graphs have large tree-width
• Graph minors. III. Planar tree-width
• Linearity of grid minors in treewidth with applications through bidimensionality
• A bound on the treewidth of planar even-hole-free graphs

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)