Graduate Thesis Or Dissertation


Structural Results and Approximation Algorithms in Minor-free Graphs Public Deposited

Downloadable Content

Download PDF


Attribute NameValues
  • Planarity has been successfully exploited to design faster and more accurate approximation algorithms for many graph optimization problems. The celebrated theorem of Kuratowski completely characterizes planar graphs as those excluding K_5 and K_{3,3} as minors. Kuratowski's theorem allows one to generalize planar graphs to H-minor-free graphs: those that exclude a fixed graph H as a minor. The deep results of Robertson and Seymour reveal many hidden structures in H-minor-free graphs, that have been used extensively in algorithmic designs. Relying on these structures, we design (i) an (efficient) polynomial time approximation scheme (PTAS) for two different variants of the traveling salesperson problem (TSP) and (ii) simple local search PTASes for r-dominating set and feedback vertex set problems. We then present several results concerning structures of planar graphs. Specifically, we make progresses on two conjectures on existence of large induced forests in planar graphs.
Resource Type
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Committee Member
Academic Affiliation
Rights Statement
Peer Reviewed
Embargo reason
  • Ongoing Research
Embargo date range
  • 2018-06-10 to 2019-07-11



This work has no parents.

In Collection: