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

DOI10.1016/j.dam.2012.01.007zbMath1242.05070DBLPjournals/dam/GrigorievMUT12OpenAlexW2009537846WikidataQ57338949 ScholiaQ57338949MaRDI QIDQ423947

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)

Cites Work

• Unnamed Item
• Unnamed Item
• Treewidth lower bounds with brambles
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Call routing and the ratcatcher
• Quickly excluding a planar graph
• On planar graphs with large tree-width and small grid minors
• Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
• All-pairs shortest paths for unweighted undirected graphs in o(mn) time
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• SOFSEM 2005: Theory and Practice of Computer Science

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