Low Polynomial Exclusion of Planar Graph Patterns

DOI10.1002/jgt.22009zbMath1359.05118arXiv1305.7112OpenAlexW2108557121MaRDI QIDQ2958196

Dimitrios M. Thilikos, Jean-Florent Raymond

Publication date: 1 February 2017

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.7112

zbMATH Keywords

treewidthgraph minors

Mathematics Subject Classification ID

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

Related Items (2)

Minors in graphs of large \(\theta_r\)-girth ⋮ Finding Detours is Fixed-Parameter Tractable

Cites Work

• Unnamed Item
• New spectral lower bounds on the bisection width of graphs
• Note on the girth of Ramanujan graphs
• Linearity of grid minors in treewidth with applications through bidimensionality
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Graph minors. V. Excluding a planar graph
• Quickly excluding a forest
• A partial k-arboretum of graphs with bounded treewidth
• Highly connected sets and the excluded grid theorem
• Existence and explicit constructions of \(q+1\) regular Ramanujan graphs for every prime power \(q\)
• Quickly excluding a planar graph
• On search, decision, and the efficiency of polynomial-time algorithms
• On interval routing schemes and treewidth
• Tree-width and planar minors
• Graph minors. II. Algorithmic aspects of tree-width
• On Linear Time Minor Tests with Depth-First Search
• Polynomial bounds for the grid-minor theorem

This page was built for publication: Low Polynomial Exclusion of Planar Graph Patterns