Minimum face-spanning subgraphs of plane graphs

Abstract

A plane graph is a planar graph with a fixed embedding. Let G = (V, E) be an edge weighted connected plane graph, where V and E are the set of vertices and edges, respectively. Let F be the set of faces of G. For each edge e ∊ E, let w(e) ≥ 0 be 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 the vertex set of H contains at least one vertex from the boundary of each face f ∊ F of G. A minimum face-spanning subgraph H of G is a face-spanning subgraph of G, where is minimum. In this paper we consider the problem of finding a minimum face-spanning subgraph of a plane graph and deal with the following problem which we call “the face-spanning subgraph problem”: “Is there any face-spanning subgraph H of G such that , for a positive real number b?”. We prove that the face-spanning subgraph problem of a plane graph is NP-complete, which implies that it is unlikely to have a polynomial time algorithm for finding a minimum face-spanning subgraph of a plane graph. In this paper, we consider a variation of the face-spanning subgraph problem called “minimum-vertex face-spanning subgraph problem” where the objective is to minimize the number of vertices instead of edge cost and we prove that the minimum-vertex face-spanning subgraph problem is also NP-complete. We also present approximation algorithms for both the problems. We calculate the approximation ratios and time complexities for both the algorithms. In this paper, we also present a linear time algorithm for finding a minimal face-spanning subgraph of a plane graph. We calculate the upper bound and lower bound on the number of vertices for a minimal face-spanning subgraph. We show that the upper bound and the lower bound are tight. Note that the graphs being dealt with in the paper are all undirected.

Keywords:

• Graphs
• NP-complete problems
• connected vertex cover
• weighted tree cover
• face-spanning subgraphs

2010 Mathematics Subject Classification:

• 05C10
• 05C85