Faces in the crowd

Abstract

We study a pair of N P-hard problems aimed at finding small sets of faces in planar graphs. In the disk dimension problem, we are given a planar graph G, and seek the least number k for which G embeds in the plane minus k open disks, with every vertex on the boundary ofsome disk. Useful properties of graphs with bounded disk dimension are derived. We show how to obtain an outerplanar subgraph of a graph of disk dimension k by removing at most 2k − 2 vertices. We use this reduction technique to obtain a tree-decomposition of width at most 2k and a linear-time 3-approximation algorithm for the pathwidth problem on graphs of fixed disk dimension. Such results were previously known only for outerplanar graphs (graphs of disk dimension one). In the related face cover problem, we are given a plane graph G, and seek the least number k of faces whose boundaries contain all the vertices of G. Although both problems are FPT, we are able to exploit the embedding that comes with face cover instances to deriva direct O(5k + N2) algorithm, where N is the input size. This is a considerable improvement over the best previously-published face cover algorithms, which rely instead on reductions to planar dominating set.