The planar connected face-dominating set problem. (c2015)

Abstract

In the Planar Connected Face-Dominating Set problem, we are given a plane graph G and asked to find a connected subgraph T of minimum weight, or order, such that the boundary of every face of G contains at least one element of T. This problem can be reduced to the planar connected red-blue dominating set problem, which is a recently studied version of the Steiner Tree problem. We study the complexity of Planar Connected Face-Dominating Set with respect to various parameterizations and present some heuristics that make use of the degree structure of real data. Inparticular, we introduce and study a greedy heuristic that is based on high-degree vertices and minimum-spanning trees. Experiments show that our approach is efficient and delivers results that are close to optimum.