Hardness of finding minimum face-spanning subgraphs of plane graphs

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.