A note on planar graphs with large width parameters and small grid-minors

DOI10.1016/J.DAM.2012.01.007zbMATH Open1242.05070DBLPjournals/dam/GrigorievMUT12OpenAlexW2009537846WikidataQ57338949 ScholiaQ57338949MaRDI QIDQ423947FDOQ423947

Authors Bert Marchal, Natalya Usotskaya, Ioan Todinca, Alexander Grigoriev

Publication date 30 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2012.01.007

zbMATH Keywords

planar graphtree-widthbranch-widthgrid-minor

Mathematics Subject Classification ID

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

Recommendations

• On planar graphs with large tree-width and small grid minors
• Tree-width and large grid minors in planar graphs
• scientific article; zbMATH DE number 1262812
• On the plane-width of graphs
• On the path-width of planar graphs
• Graph minors. III. Planar tree-width
• On the tree-width of planar graphs
• The plane-width of graphs
• Minor-minimal planar graphs of even branch-width
• Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality

Cites work

• A partial k-arboretum of graphs with bounded treewidth
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Call routing and the ratcatcher
• Graph minors. X: Obstructions to tree-decomposition
• Graph theory
• Improved bounds on the planar branchwidth with respect to the largest grid minor size
• On planar graphs with large tree-width and small grid minors
• Optimal branch-decomposition of planar graphs in \(O(n^3)\) time
• Quickly excluding a planar graph
• SOFSEM 2005: Theory and Practice of Computer Science
• Tree-width and large grid minors in planar graphs
• Treewidth lower bounds with brambles

Cited in

(3)

• On planar graphs with large tree-width and small grid minors
• The effect of planarization on width
• Improved bounds on the planar branchwidth with respect to the largest grid minor size

This page was built for publication: A note on planar graphs with large width parameters and small grid-minors

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