ERA

Download the full-sized PDF of Polygon Graph RecognitionDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3CJ87M8N

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Polygon Graph Recognition Open Access

Descriptions

Author or creator
Elmallah, Ehab
Stewart, Lorna
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 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.
Date created
1995
DOI
doi:10.7939/R3CJ87M8N
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-29T15:05:44.546+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 750608
Last modified: 2015:10:12 17:30:26-06:00
Filename: TR95-03.pdf
Original checksum: 63a0b3f1fbd32108d55d88b4eec1d4d4
Well formed: true
Valid: true
Page count: 35
Activity of users you follow
User Activity Date