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, Perugia, Italy , 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
ID Code:427

Repository Staff Only: item control page

References

A. Bouchet: Circle graph obstructions, J. Comb. Theory, Ser. B 60, No. 1 (1994) 107-144

E. M. Eschen, J. P. Spinrad: An O(n^{2}) algorithm for cicular-arc graph recognition, in: Proceedings 4th ACM-SIAM Symposium on Discrete Algorithms, (1993), 128-137

H. de Fraysseix: A characterization of circle graphs, Eur. J. Comb. 5 (1984) 223-238

P. C. Gilmore, A. J. Hoffman: A characterization of comparability graphs and of interval graphs, Can. J. Math. 16 (1964) 539-548

A. Gyarfás: Problems from the world surrounding perfect graphs, Zastosow. Mat. 19. No. 3/4 (1987) 413-441

I. Holyer: The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 713-717

M. Koebe: On a New Class of Intersection Graphs, Proceedings of the Fourth Czechoslovak Symposium on Combinatorics Prachatice, 141-143, 1990

J. Kratochvíl, String graphs II. Recognizing string graphs is NP-hard, J. Combin. Theory Ser. B, 52 (1991), 67-78.

J. Kratochvíl, A. Kostochka: Covering and coloring polygon-circle graphs, Discrete Math. 163 (1997) 29-9-305

J. Kratochvíl, A. Lubiw, and J. Nesetril: Noncrossing subgraphs of topological layouts, SIAM J. Discrete Math. 4 (1991) 223-244

J. Kratochvíl, J. Matousek: String graphs requiring exponential representations, J. Combin. Theory Ser. B 53 (1991) 1-4

J. Pach, G. Tóth: Recognizing string graphs is decidable, In: Graph Drawing (P. Mutzel, M. Jünger and S. Leipert, eds.), Proceedings 9th International Symposium GD 2001, Vienna 2001, Lecture Notes in Computer Science 2265, Springer Verlag Berlin Heidelberg 2002, pp. 247-260

J. P. Spinrad: Recognition of Circle Graphs, Journal of Algorithms 16(1), 264-282, 1994

J. P. Spinrad: http://www.vuse.vanderbilt.edu/~spin/open.html

M. Schaefer, D. Stefankovic: Decidability of string graphs, In: STOC 2001, Proceedings 33rd Annual ACM Symposium on Theory of Computing, Greece 2001, pp. 241-246

M. Schaefer, E. Sedgwick and D. Stefankovic: Recognizing string graphs in NP, In: STOC 2002, Proceedings 34rd Annual ACM Symposium on Theory of Computing

A. C. Tucker: An efficient test for circular-arc graphs, SIAM J. Comput. 9 (1980) 1-24