Cover Contact Graphs

CCCG 2012, Charlottetown, P.E.I., August 8–10, 2012

The Cover Contact Graph of Discs Touching a Line
Stephane Durocher∗ Saeed Mehrabi∗ Matthew Skala∗ Mohammad Abdul Wahid∗

Abstract We answer a question of Atienza et al. [4] by showing that the circular CCG+ problem is N P-complete. If we cover a set of objects on the plane with discs whose interiors are pairwise disjoint, then we can forma cover contact graph (CCG) that records which of the covering discs touch at their boundaries. When the input objects are themselves discs, and both input and covering discs are constrained to be touching and above the x-axis, then the circular CCG+ problem is to decide the existence of a covering with a connected CCG. We also define an approximate version of this problem by allowing a smalloverlap between covering discs, and give an algorithm that in polynomial time finds an approximate solution for any yes-instance of the exact problem. 1 Introduction

Given a set S of n disjoint input discs in the plane, a covering C of S consists of n covering discs such that each covering disc covers exactly one input disc and no two covering discs intersect except on their boundaries. In general,the radii of the covering discs need not all be the same. The cover contact graph (CCG) induced by C is a graph G = (V, E) such that each input disc corresponds to a vertex in V and two vertices are connected by an edge if and only if their corresponding covering discs are tangent. In other words, G is the intersection graph of a set of discs in the plane whose interiors are pairwise disjoint.Koebe’s theorem [6] states that every planar graph can be represented as a coin graph. The coin graph of a set of discs in the plane is in fact the CCG of that set of discs. Problems related to these graphs arise in many application areas, such as wireless communication networks [5] and facility location [7]. Given a set of discs in the plane, the circular CCG problem asks if the given set admits acovering whose CCG is connected. Atienza et al. [4] show that the circular CCG problem is N P-hard using a reduction from Planar3Sat, a constrained version of 3Sat in which the corresponding variable-clause graph must be planar. They also explore a variant in which the input discs are reduced to distinct points, with different kinds of connectivity required for the contact graph. They
∗ Departmentof Computer Science, University of Manitoba, {durocher, mehrabi, mskala, wahid}@cs.umanitoba.ca

give algorithms with O(n log n) worst-case running time for 1-connectivity, and with O(n2 log n) expected running time for 2-connectivity. They also study variants in which the covering discs are required to touch the xaxis. While they extensively examine the axis-touching case when the input islimited to distinct points, they leave open the case where the input is a set of discs and both the input and the covering discs are required to touch the x-axis. This is the circular CCG+ problem, for which we show N P-hardness in this paper. Our proof depends on very precise differences in the radii of the discs, and we show that such differences are essential to the hardness of the problem. We definean -approximate version of the circular CCG+ problem and give a polynomial-time algorithm such that if the circular CCG+ problem has an exact solution, then our algorithm produces an -approximate solution. Many related problems are known. One is that of realizability. In addition to the set of input discs, we can be given an unlabeled planar graph G and the goal of deciding whether there exists acovering for the given input set whose CCG is G. Atienza et al. [4] show, again by reduction from Planar3Sat, that this realizability problem is also N P-hard, even if the input is a set of points. Notwithstanding Koebe’s theorem that every planar graph is realizable as a coin graph (without constraining the centres of the discs), if we fix the coordinates of the vertices to make a geometric graph...