planar graph

Feedback vertex sets and disjoint cycles in planar (di)graphs

  • Ton Kloks
  • Chuan Min Lee
  • Jim Liu
    • Categories Graphs and Matroids Tags , , ,

    We present new fixed parameter algorithms for feedback vertex set and disjoint cycles on planar graphs. We give an $O(c^{\sqrt{k}} + n)$ algorithm for $k$-feedback vertex set and an $O(c^{\sqrt{k}} n)$ algorithm for $k$-disjoint cycles on planar graphs. CitationManuscript 4 July, 2001.ArticleDownload View PDF