2004 | OriginalPaper | Chapter
Two Results on Intersection Graphs of Polygons
Authors : Jan Kratochvíl, Martin Pergel
Published in: Graph Drawing
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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 − log2n + o(log2n) by showing that for every positive constant c < 1,cmp(n) ≤ n − clogn 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 − 2 loglogn corners. We also show that recognizing intersection graphs of k-gons inscribed in a circle is an NP-complete problem for every fixed k ≥ 3.