This is a decommissioned version of ERA which is running to enable completion of migration processes. All new collections and items and all edits to existing items should go to our new ERA instance at https://ualberta.scholaris.ca - Please contact us at erahelp@ualberta.ca for assistance!
- 229 views
- 265 downloads
Polygon Graph Recognition
-
- Author(s) / Creator(s)
-
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
-
- Type of Item
- Report
-
- License
- Attribution 3.0 International