There are by now mountains of results on separators in graphs, from planar separator, tree separator, bounded tree width graphs, bounded genus graphs, etc, etc, etc. Is there any good updated survey about this, and their applications?

  • $\begingroup$ Time for you to write one Sariel :). $\endgroup$ – Chandra Chekuri Aug 3 '13 at 19:52
  • $\begingroup$ I was hoping you would write it Chandra ;). $\endgroup$ – Sariel Har-Peled Aug 16 '13 at 5:56

Not exactly the most recent (published in 2001), but the text by Arnold L. Rosenberg, Lenwood S. Heath, "Graph Separators, with Applications" may be a good place to look. The Google book link is provided here: http://books.google.ca/books/about/Graph_Separators_with_Applications.html?id=7DNKE5ZiNZYC&redir_esc=y

  • 4
    $\begingroup$ Yeh. I was hoping for something more updated than this. (I definitely saw this book before - I think it had the answer to one of my previous questions on this forum). There was a lot of nice recent work on planar graphs using separators - it would be nice to have a good survey of this stuff... $\endgroup$ – Sariel Har-Peled Aug 2 '13 at 3:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.