Abstract:
In this research work, we have introduced a new graph problem namely "minimum facespanning
subgraph problem". Let G be an edge weighted connected plane graph, let
V (G) and E( G) be the set of vertices and edges, respectively. Let F be the set of faces of
graph G. For each edge e E; E, w( e) 2: 0 is the weight of the edge e of G. A face-spanning
subgraph of G is a connected subgraph H induced by a set of edges S <:;; E such that S
contains at least one vertex from the boundary of each face f E F of G. The minimum
face-spanning subgraph problem asks to find a face-spanning subgraph H induced by S
of G such that cost of H is minimum. Finding a minimum face-spanning subgraph has
practical applications in planning irrigation canal networks in irrigation systems, planning
gas pipelines in a locality, layout of power supply lines in a printed circuit board etc.
Efficient algorithms are necessary to solve these kinds of problems which arise from
numerous practical applications. However developing efficient algorithms is not always
possible. In this thesis, we show that finding an efficient algorithm for solving the minimum
face-spanning subgraph problem is unlikely by showing that this problem belongs to
the infamous class of NP-complete problems. We also prove that a variation of the minimum
face-spanning subgraph problem called "minimum-vertex face-spanning subgraph
problem" is NP-complete. Since it is unlikely to have efficient algorithms for both the
problems, design of approximation algorithms is an urgent need. We present approximation
algorithms for both the problems in this thesis. Approximation ratio and complexity
analysis of the developed approximation algorithms are also presented in this thesis.
