CAN VISIBILITY GRAPHS BE REPRESENTED COMPACTLY

We consider the problem of representing the visibility graph of line s egments as a union cliques and bipartite cliques. Given a graph G, a f amily {G = G(1), G(2), ...G(k)} is called a clique cover G if (i) each G(i) is a clique or a bipartite clique, and (ii) the union of G(i) is G. The size of the clique cover G is defined as Sigma(i=1) (k) n(i), where n(i) is the number of vertices in G(i). Our main result is that there are visibility graphs of n nonintersecting line segments in the plane whose smallest clique cover has size Omega(n(2)/log(2) n). An up per bound of O(n(2)/log n) on the clique cover follows from a well-kno wn result in extremal graph theory. On the other hand, we show that th e visibility graph of a simple polygon always admits a clique cover th e size O(n log(3) n), and that there are simple polygons whose visibil ity graphs require a clique cover of size Omega(n log n).