Two Results on Intersection Graphs of PolygonsKratochvíl, Jan and Pergel, Martin (2004) Two Results on Intersection Graphs of Polygons. In: Graph Drawing 11th International Symposium, GD 2003, September 2124, 2003 , pp. 5970(Official URL: http://dx.doi.org/10.1007/9783540245957_6). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540245957_6
AbstractIntersection graphs of convex polygons inscribed to a circle, so called polygoncircle graphs, generalize several well studied classes of graphs, e.g., interval graphs, circle graphs, circulararc graphs and chordal graphs. We consider the question how complicated need to be the polygons in a polygoncircle representation of a graph. Let cmp(n) denote the minimum k such that every polygoncircle graph on n vertices is the intersection graph of kgons inscribed to the circle. We prove that cmp(n) = nlog_{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 polygoncircle graphs on n vertices which are not representable by polygons with less than nlogn2loglogn corners. We also show that recognizing intersection graphs of kgons inscribed in a circle is an NPcomplete problem for every fixed k \ge 3.
Actions (login required)
