In an alternative approach to "characterizing" the graph class of visibility graphs of simple polygons, we study the problem of finding a maximum clique in the visibility graph of a simple polygon with n vertices. We show that this problem is very hard, if the input polygons are allowed to contain holes: a gap-preserving reduction from the maximum clique problem on general graphs implies that no polynomial time algorithm can achieve an approximation ratio of n sup(1/8-∈) for any, unless NP=P. To demonstrate that allowing holes in the input polygons makes a major difference, we propose an O(n sup（3）) algorithm for the maximum clique problem on visibility graphs for polygons without holes (other O(n sup（3）) algorithms for this problem are already known [3,6,7]). Our algorithm also finds the maximum weight clique, if the polygon vertices are weighted.
展开▼
