Summary: For any fixed integer \(k\geq 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^kn^2)\) time. Then 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.