Two Results on Intersection Graphs of Polygons

Kratochvíl, Jan and Pergel, Martin (2004) Two Results on Intersection Graphs of Polygons. In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003 , pp. 59-70(Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_6).

Full text not available from this repository.

Abstract

Intersection graphs of convex polygons inscribed to a circle, so called polygon-circle graphs, generalize several well studied classes of graphs, e.g., interval graphs, circle graphs, circular-arc graphs and chordal graphs. We consider the question how complicated need to be the polygons in a polygon-circle representation of a graph. Let cmp(n) denote the minimum k such that every polygon-circle graph on n vertices is the intersection graph of k-gons inscribed to the circle. We prove that cmp(n) = n-log_{2}n + o(log_{2}n) by showing that for every positive constant c < 1, cmp(n) \le n - c log n for every sufficiently large n, and by providing an explicit construction of polygon-circle graphs on n vertices which are not representable by polygons with less than n-logn-2loglogn corners. We also show that recognizing intersection graphs of k-gons inscribed in a circle is an NP-complete problem for every fixed k \ge 3.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-540-24595-7_6
Classifications: Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/427

Actions (login required)

View Item View Item