The Cover Contact Graph of Discs Touching a Line.
Stéphane Durocher, Saeed Mehrabi, Matthew Skala, Mohammad Abdul Wahid · 2012
We answer a question of Atienza et al. [4] by showing that the circular CCG+ problem is NP-complete. If we cover a set of objects on the plane with discs whose in-teriors are pairwise disjoint, then we can form a cover contact graph (CCG) that records which of the cover-ing discs touch at their boundaries. When the input objects are themselves discs, and both input and cover-ing 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 allow-ing a small overlap between covering discs, and give an algorithm that in polynomial time finds an approximate solution for any yes-instance of the exact problem. 1