Polygon Graph RecognitionReport as inadecuate




Polygon Graph Recognition - Download this document for free, or read online. Document in PDF available to download.

graph algorithms, graph theory

Additional contributors:

Subject-Keyword: graph algorithms graph theory

Type of item: Computing Science Technical Report

Computing science technical report ID: TR95-03

Language: English

Place:

Time:

Description: 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 O4^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.

Date created: 1995

DOI: doi:10.7939-R3CJ87M8N

License information: Creative Commons Attribution 3.0 Unported

Rights:





Author: Elmallah, Ehab Stewart, Lorna

Source: https://era.library.ualberta.ca/


Teaser



University of Alberta Polygon Graph Recognition by E.S.
Elmallah and L.K.
Stewart Technical Report TR 95{03 February 1995 DEPARTMENT OF COMPUTING SCIENCE The University of Alberta Edmonton, Alberta, Canada Polygon Graph Recognition E.S.
Elmallah and L.K.
Stewart Department of Computing Science University of Alberta Edmonton, Alberta, T6G 2H1 CANADA Abstract For any xed integer 2, de ne the class of -polygon graphs as the intersection graphs of chords inside a convex -polygon, where the endpoints of each chord lie on two dierent sides.
The case where = 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 -polygon graphs, for any xed , given a polygon representation of the input graph.
In this paper we show that determining whether a given circle graph is a -polygon graph, for any xed , can be solved in (4k 2) time.
The algorithm exploits the structure of a decomposition tree of the input graph and produces a -polygon representation, if one exists.
In contrast, we show that determining the minimum value of is NP-complete.
1 k k k k k k k k k k Keywords: graph algorithms, graph theory 1 This research is partially supported by NSERC Operating Grants 1 O n 1.
Introduction This paper investigates the complexity of the following class of recognition problems: given an undirected graph G = (V E ), and an integer k, k 2, is G a k-polygon graph? That is, does there exist a one-to-one mapping between V and chords of a k-polygon such that (vi vj ) 2 E if and only if their corresponding chords intersect? The case where k = 2 is degenerate but important for our purpose we view any pair of parallel lines as a 2-polygon. If the answer is positive, then we are interested in generating the corresponding intersection diagram.
We henceforth let jV j = n and jE j = ...





Related documents