Topics for the Seminar

Intersection Graphs and Intersection Patterns

Sommer Term 2021
Stefan Felsner

1. Jacob Fox and János Pach:
   Coloring K_k-free intersection graphs of geometric objects in the plane
   Eur. J. Comb. 33(5): 853-866 (2012)
   [FP12]
   

2. János Pach and István Tomon:
   On the Chromatic Number of Disjointness Graphs of Curves.
   Symposium on Computational Geometry 2019: 54:1-54:17
   [PT19]
   

3. Holmsen, Andreas F.; Mojarrad, Hossein Nassajian; Pach, János; Tardos, Gábor
   Two extensions of the Erdős-Szekeres problem
   J. Eur. Math. Soc. 22, 3981-3995 (2020)
   [HMPT20]
   

4. János Pach, József Solymosi & Géza Tóth:
   Unavoidable Configurations in Complete Topological Graphs
   Discret. Comput. Geom. 30(2): 311-320 (2003)
   [PST03]
   

5. Josef Cibulka, Pu Gao, Marek Krčál, Tomáš Valla & Pavel Valtr
   On the Geometric Ramsey Number of Outerplanar Graphs
   Comput. Geom. 53(1): 64-79 (2015)
   [CGKVV15]
   

6. Daniel Gonçalves, Lucas Isenmann, and Claire Pennarun
   Planar Graphs as L-intersection or L-contact graphs
   Symp. on Discr. Alg. (SODA) 2018: 172--184
   [GIP18]
   

7. Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michal Lason, Piotr Micek, William T. Trotter, Bartosz Walczak:
   Triangle-Free Geometric Intersection Graphs with Large Chromatic Number
   Discret. Comput. Geom. 50(3): 714-726 (2013)
   [PK+13]
   

8. Daniel Heldt, Kolja Knauer & Torsten Ueckerdt:
   Edge-intersection graphs of grid paths: The bend-number
   Discret. Appl. Math. 167: 144-162 (2014)
   [HKU14]
   

9. Pankaj K. Agarwal, Eran Nevo, János Pach, Rom Pinchasi, Micha Sharir & Shakhar Smorodinsky:
   Lenses in arrangements of pseudo-circles and their applications
   Jour. ACM 51(2): 139-186 (2004)
   [ANPPSS04]
   

10. László Lovász: 
    Graphs and Geometry; Chapter 6 - square contacts
    AMS Colloquium Publications, Volume: 65; 2019.
    [Lov19]
    

11. Jiří Matoušek
    String graphs and separators
    Geometry, Structure and Randomness in Combinatorics pp 61-97, Springer 2014.
    [Mat14]
    

12. 
    Mihalis Yannakakis: Embedding Planar Graphs in Four Pages.
    J. Comput. Syst. Sci. 38(1): 36-67 (1989)
    [Yan89]
    Michael A. Bekos, Michael Kaufmann, Fabian Klute, Sergey Pupyrev, Chrysanthi N. Raftopoulou, Torsten Ueckerdt:
    Four Pages Are Indeed Necessary for Planar Graphs. J. Comput. Geom. 11(1): 332-353 (2020)
    [BK+20]
    Mihalis Yannakakis: Planar graphs that need four pages.
    J. Comb. Theory, Ser. B 145: 241-263 (2020)
    [Yan20]
    
    

13. Vida Dujmovic, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, David R. Wood:
    Planar Graphs Have Bounded Queue-Number.
    J. ACM 67(4): 22:1-22:38 (2020)
    [DJ+20]
    

14. Parinya Chalermsook, Bartosz Walczak
    Coloring and Maximum Weight Independent Set of Rectangles
    arXiv:2007.07880
    [CW20]
    

15. Adam Marcus, Gábor Tardos:
    Intersection reverse sequences and geometric applications.
    J. Comb. Theory, Ser. A 113(4): 675-691 (2006)
    [MT06]
    

16. Andrew Suk, Bartosz Walczak:
    New bounds on the maximum number of edges in k-quasi-planar graphs.
    Comput. Geom. 50: 24-33 (2015)
    [SW15]
    

17. János Pach, Natan Rubin, Gábor Tardos:
    On the Richter-Thomassen Conjecture about Pairwise Intersecting Closed Curves.
    Comb. Probab. Comput. 25(6): 941-958 (2016)
    [PRT16]