Optimizing the graph minors weak structure theorem

Archontia C. Giannopoulou, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

Abstract

One of the major results of [N. Robertson and P. D. Seymour, Graph minors. XIII. The disjoint paths problem, J. Combin. Theory Ser. B, 63 (1995), pp. 65-110], also known as the weak structure theorem, reveals the local structure of graphs excluding some graph as a minor: each such graph G either has small treewidth or contains the subdivision of a planar graph (a wall) that can be arranged in a flat manner inside G, given that some small set of vertices is removed. We prove an optimized version of that theorem where (i) the relation between the treewidth of the graph and the height of the wall is linear (thus best possible) and (ii) the number of vertices to be removed is minimized.

Original languageEnglish (US)
Pages (from-to)1209-1227
Number of pages19
JournalSIAM Journal on Discrete Mathematics
Volume27
Issue number3
DOIs
StatePublished - 2013

Keywords

  • Graph minors
  • Treewidth

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Optimizing the graph minors weak structure theorem'. Together they form a unique fingerprint.

Cite this