License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2016.31
URN: urn:nbn:de:0030-drops-60546
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6054/
Go to the corresponding LIPIcs Volume Portal

Chuzhoy, Julia

Excluded Grid Theorem: Improved and Simplified (Invited Talk)

pdf-format:
LIPIcs-SWAT-2016-31.pdf (0.2 MB)

Abstract

One of the key results in Robertson and Seymour's seminal work on graph minors is the Excluded Grid Theorem. The theorem states that there is a function f, such that for every positive integer g, every graph whose treewidth is at least f(g) contains the (gxg)-grid as a minor. This theorem has found many applications in graph theory and algorithms. An important open question is establishing tight bounds on f(g) for which the theorem holds. Robertson and Seymour showed that f(g)>= \Omega(g^2 log g), and this remains the best current lower bound on f(g). Until recently, the best upper bound was super-exponential in g. In this talk, we will give an overview of a recent sequence of results, that has lead to the best current upper bound of f(g)=O(g^{19}polylog(g)). We will also survey some connections to algorithms for graph routing problems.

BibTeX - Entry

@InProceedings{chuzhoy:LIPIcs:2016:6054,
  author =	{Julia Chuzhoy},
  title =	{{Excluded Grid Theorem: Improved and Simplified (Invited Talk)}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{31:1--31:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6054},
  URN =		{urn:nbn:de:0030-drops-60546},
  doi =		{10.4230/LIPIcs.SWAT.2016.31},
  annote =	{Keywords: Graph Minor Theory, Excluded Grid Theorem, Graph Routing}
}

Keywords: Graph Minor Theory, Excluded Grid Theorem, Graph Routing
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI