Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6868454 | Computational Geometry | 2018 | 8 Pages |
Abstract
Let S={p1,p2,â¦,pn} be a set of pairwise disjoint geometric objects of some type in a 2D plane and let C={c1,c2,â¦,cn} be a set of closed objects of some type in the same plane with the property that each element in C covers exactly one element in S and any two elements in C are interior-disjoint. We call an element in S a seed and an element in C a cover. A cover contact graph (CCG) has a vertex for each element of C and an edge between two vertices whenever the corresponding cover elements touch. It is known how to construct, for any given point seed set, a disk or triangle cover whose contact graph is 1- or 2-connected but the problem of deciding whether a k-connected CCG can be constructed or not for k>2 is still unsolved. A triangle cover contact graph (TCCG) is a cover contact graph whose cover elements are triangles. In this paper, we give algorithms to construct a 3-connected TCCG and a 4-connected TCCG for a given set of point seeds. We also show that any connected outerplanar graph has a realization as a TCCG on a given set of collinear point seeds. Note that, under this restriction, only trees and cycles are known to be realizable as CCG.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Shaheena Sultana, Md. Iqbal Hossain, Md. Saidur Rahman, Nazmun Nessa Moon, Tahsina Hashem,