Can visibility graphs Be represented compactly?

We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graphG, a familyG={G ₁,G ₂,...,G _k } is called aclique cover ofG if (i) eachG _i is a clique or a bipartite clique, and (ii) the union ofG _i isG. The size of the clique coverG is defined as ∑ _i=1 ^k n _i , wheren _i is the number of vertices inG _i . Our main result is that there are visibility graphs ofn nonintersecting line segments in the plane whose smallest clique cover has size Ω(n ²/log² n). An upper bound ofO(n ²/logn) on the clique cover follows from a well-known result in extremal graph theory. On the other hand, we show that the visibility graph of a simple polygon always admits a clique cover of sizeO(nlog³ n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n logn). The work by the first author was supported by National Science Foundation Grant CCR-91-06514. The work by the second author was supported by a USA-Israeli BSF grant. The work by the third author was supported by National Science Foundation Grant CCR-92-11541.