I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone here can help me find one.

Thanks in advance.


1 Answer 1


I haven't got any paper, but looking through my favorite book regarding approximation algorithms i've got something.

It is named: The Design of Approximation Algorithms. You find it free for download (even legal) on https://www.designofapproxalgs.com.

Take a look at page 269 (ff.) especially page 271 should be interesting for you as they describe and proof a PTAS for max independent set in planar graphs.

It might not be "front of the line" research or results but hope it helps.

  • $\begingroup$ It definitely helps so thank you :) $\endgroup$
    – Maitgon
    Jun 19, 2020 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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