Can visibility graphs be represented compactly?

Pankaj K. Agarwal, Noga Alon, Boris Aronov, Subhash Suri

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    Abstract

    We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G = {G1, G2,..., Gk} is called a clique cover of G if (i) each Gi is a clique or a bipartite clique, and (ii) the union of Gi is G. The size of the clique cover G is defined as Σik=1 ni, where ni is the number of vertices in Gi. Our main result is that there exist visibility graphs of n nonintersecting line segments in the plane whose smallest clique cover has size Ω(n2/log2 n). An upper bound of O(n2/log n) 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 a size O(n log3 n), and that there are simple polygons whose visibility graphs require a clique cover of size Ω(n log n).

    Original languageEnglish (US)
    Title of host publicationProceedings of the 9th Annual Symposium on Computational Geometry
    PublisherPubl by ACM
    Pages338-347
    Number of pages10
    ISBN (Print)0897915828, 9780897915823
    DOIs
    StatePublished - 1993
    EventProceedings of the 9th Annual Symposium on Computational Geometry - San Diego, CA, USA
    Duration: May 19 1993May 21 1993

    Publication series

    NameProceedings of the 9th Annual Symposium on Computational Geometry

    Other

    OtherProceedings of the 9th Annual Symposium on Computational Geometry
    CitySan Diego, CA, USA
    Period5/19/935/21/93

    ASJC Scopus subject areas

    • Engineering(all)

    Fingerprint Dive into the research topics of 'Can visibility graphs be represented compactly?'. Together they form a unique fingerprint.

  • Cite this

    Agarwal, P. K., Alon, N., Aronov, B., & Suri, S. (1993). Can visibility graphs be represented compactly? In Proceedings of the 9th Annual Symposium on Computational Geometry (pp. 338-347). (Proceedings of the 9th Annual Symposium on Computational Geometry). Publ by ACM. https://doi.org/10.1145/160985.161160