Maximum Independent Set in 2-Direction Outersegment Graphs

1. Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph classes: a survey. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics Mathematics (1999)

   Google Scholar 

2. Flier, H., Mihalák, M., Schöbel, A., Widmayer, P., Zych, A.: Vertex Disjoint Paths for Dispatching in Railways. In: Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS), Schloss Dagstuhl–Leibniz-Zentrum für Informatik, vol. 14, pp. 61–73 (2010)

   Google Scholar 

3. Fox, J., Pach, J.: Coloring K _k -free intersection graphs of geometric objects in the plane. In: Proceedings of the 24th ACM Symposium on Computational Geometry (SoCG), pp. 346–354. ACM (2008)

   Google Scholar 

4. Fox, J., Pach, J.: Erdős-Hajnal-type results on intersection patterns of geometric objects. In: Győri, E., Katona, G.O.H., Lovász, L. (eds.) Horizons of Combinatorics, vol. 17, pp. 79–103. Springer, Heidelberg (2008)

   Chapter  Google Scholar 

5. Fox, J., Pach, J.: A separator theorem for string graphs and its applications. Combinatorics, Probability and Computing 19(03), 371–390 (2010)

   Article  MathSciNet  MATH  Google Scholar 

6. Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters 73(5-6), 181–188 (2000)

   Article  MathSciNet  MATH  Google Scholar 

7. Mark Keil, J.: The complexity of domination problems in circle graphs. Discrete Applied Mathematics 42(1), 51–63 (1993)

   Article  MathSciNet  MATH  Google Scholar 

8. Kratochvíl, J.: String graphs. I. The number of critical nonstring graphs is infinite. Journal of Combinatorial Theory, Series B 52(1), 53–66 (1991)

   Article  MathSciNet  MATH  Google Scholar 

9. Kratochvíl, J.: String graphs. II. Recognizing string graphs is NP-hard. Journal of Combinatorial Theory, Series B 52(1), 67–78 (1991)

   Article  MathSciNet  MATH  Google Scholar 

10. Kratochvíl, J., Matoušek, J.: String graphs requiring exponential representations. Journal of Combinatorial Theory, Series B 53(1), 1–4 (1991)

    Article  MathSciNet  MATH  Google Scholar 

11. Kratochvíl, J., Nešetřil, J.: INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Commentationes Mathematicae Universitatis Carolinae 31(1), 85–93 (1990)

    MathSciNet  MATH  Google Scholar 

12. Middendorf, M., Pfeiffer, F.: The max clique problem in classes of string-graphs. Discrete Mathematics 108(1-3), 365–372 (1992)

    Article  MathSciNet  MATH  Google Scholar 

13. Pach, J., Tóth, G.: Recognizing string graphs is decidable. Discrete & Computational Geometry 28, 593–606 (2002)

    Article  MathSciNet  MATH  Google Scholar 

14. Schaefer, M., Sedgwick, E., Štefankovič, D.: Recognizing string graphs in NP. Journal of Computer and System Sciences 67(2), 365–380 (2003); Special Issue on STOC 2002

    Article  MathSciNet  MATH  Google Scholar 

15. Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Springer, Heidelberg (2003)

    MATH  Google Scholar 

16. Unger, W.: On the k-colouring of circle-graphs. In: Cori, R., Wirsing, M. (eds.) STACS 1988. LNCS, vol. 294, pp. 61–72. Springer, Heidelberg (1988)

    Chapter  Google Scholar 

Download references