# Polygon Graph Recognition

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 = ...