1
$\begingroup$

Can someone recommend a reference on graph minors structure theorem and sublinear treewidth? Doesn't have to be the newest/strongest results as long as it's easier than tracking down all the papers written about these results.

Mostly I'm interested in finding the details about the existence of large grid minors in large treewidth planar and minor free graphs and sublinear treewidth of planar and minor free graphs from basic graph theory.

$\endgroup$
5
  • 2
    $\begingroup$ The book parameterized-algorithms.mimuw.edu.pl/… chapter 7.7 $\endgroup$ – Laakeri Dec 27 '20 at 20:45
  • $\begingroup$ @Laakeri I meant covering the proof of sublinear treewidth $\endgroup$ – Hao S Dec 27 '20 at 20:48
  • 3
    $\begingroup$ What exactly do you mean by the "proof" of sub-linear treewidth? It is an easy consequence of separator theorems for planar graphs and more generally minor free graphs. $\endgroup$ – Chandra Chekuri Dec 27 '20 at 23:06
  • $\begingroup$ @ChandraChekuri I guess I mean from reasonably basic graph theory basically anything that's easier than tracking down all the related papers $\endgroup$ – Hao S Dec 28 '20 at 23:46
  • 1
    $\begingroup$ You may find some references here useful. cstheory.stackexchange.com/questions/44317/… $\endgroup$ – Chandra Chekuri Dec 29 '20 at 0:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.