 10 views
 58 downloads
Polygon Graph Recognition

 Author(s) / Creator(s)

Technical report TR9503. For any fixed integer k >= 2, define the class of kpolygon graphs as the intersection graphs of chords inside a convex kpolygon, 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 2polygon. 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 kpolygon 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 kpolygon 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 kpolygon representation, if one exists. In contrast, we show that determining the minimum value of k is NPcomplete.  TRIDID TR9503

 Date created
 1995

 Subjects / Keywords

 Type of Item
 Report

 License
 Attribution 3.0 International