Numerous computational problems on graphs remain computationally intractable and are termed NP-complete problems. In this thesis, we study one of the ways to tackle this issue: we restrict the input graphs by specifying ...