Logo

Login | Create Account

Two Results on Intersection Graphs of Polygons

Kratochvíl, Jan and Pergel, Martin (2004) Two Results on Intersection Graphs of Polygons. [Conference Paper]

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
Classifications:Z Theory > Z.250 Geometry
ID Code:427
Deposited By:Maciejak, Agnes
Deposited On:02 Dec 2004
Last Modified:18 Sep 2008 13:08
Alternative Locations:http://www.springerlink.com/openurl.asp?genre=article&issn=0302-9743&volume=2912&spage=59

Repository Staff Only: item control page

References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

GDEA is powered by EPrints 3 which is developed by the School of Electronics and Computer Science at the University of Southampton. More information and software credits.