POLYGON GRAPH RECOGNITION

For any fixed integer k greater than or equal to 2, define the class o f k-polygon graphs as the intersection graphs of chords inside a conve x k-polygon, where the endpoints of each chord lie on two different si des. 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 c ircle graphs. Interest in such graphs arises since a number of intract able problems on circle graphs can be solved in polynomial time on k-p olygon graphs, for any fixed k, given a polygon representation of the input graph. In this paper we show that determining whether a given ci rcle 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 o ne exists. In contrast, we show that determining the minimum value of k is NP-complete. (C) 1998 Academic Press.