Polygon Graph Recognition

✍ Scribed by E.S. Elmallah; L.K. Stewart

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 335 KB
• Volume: 26
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0883

✦ Synopsis

For any fixed integer k G 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 s 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 Ž k 2 . fixed k, can be solved in O 4 n 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.