Polygon Graph Recognition

• Author(s) / Creator(s)

  • Stewart, Lorna
  • Elmallah, Ehab

• Technical report TR95-03. For any fixed integer k >= 2, define the class of k-polygon graphs as the intersection graphs of chords inside a convex k-polygon, where the endpoints of each chord lie on two different sides. The case where k=2 is degenerate; for our purpose, we view any pair of parallel lines as a 2-polygon. Hence, polygon graphs are all circle graphs. Interest in such graphs arises since a number of intractable problems on circle graphs can be solved in polynomial time on k-polygon graphs, for any fixed k, given a polygon representation of the input graph. In this paper we show that determining whether a given circle graph is a k-polygon graph, for any fixed k, can be solved in O(4^k n^2) time. The algorithm exploits the structure of a decomposition tree of the input graph and produces a k-polygon representation, if one exists. In contrast, we show that determining the minimum value of k is NP-complete. | TRID-ID TR95-03

• Date created

  1995

• Subjects / Keywords

  • Graph theory
  • Graph algorithms

• Type of Item

  Report

• DOI

  https://doi.org/10.7939/R3CJ87M8N

• License

  Attribution 3.0 International