Seminar Geometry: Combinatorics and Algorithms FS18 (263-4203-00L)

Luis Barba,	CAB G33.3,	Tel: 044-632 77 96,	firstname.lastname@inf.ethz.ch
Michael Hoffmann,	CAB G33.1,	Tel: 044-632 73 90,	lastname@inf.ethz.ch
Pavel Valtr,	CAB G19.2,		firstname.lastname@inf.ethz.ch
Emo Welzl,	CAB G39.2,	Tel: 044-632 73 70,	firstname@inf.ethz.ch

Contents

This seminar is held once a year and complements the course Geometry: Combinatorics & Algorithms. Students of the seminar will present original research papers, some classic and some of them very recent. The seminar is a good preparation for a master, diploma, or semester thesis in the area.

To attend the seminar, some background in (discrete and computational) geometry and in graphs and algorithms is required. Thus, previous participation in the course "Geometry: Combinatorics & Algorithms" is a prerequisite.

Dates

First meeting: Friday Feb 23rd 2018, 13:15, CAB G15.2.

Schedule

• April 27, 2018, 13:15-14:00: Jan Studený
  B. Aronov, P. Erdös, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach and L. J. Schulman, Crossing families, Algorithms and Combinatorics, vol 14. Springer, Berlin, Heidelberg, 1997. [DOI]
  P. Valtr, On Mutually Avoiding Sets, Combinatorica, 14: 127-134, 1994. [DOI]
• April 27, 2018, 14:30-15:15: Patrick Schnider
  J. L. Álvarez Rebollar, J. Cravioto Lagos and J. Urrutia, Crossing families and self crossing Hamiltonian cycles, In Proceedings of EGC, 2015. [PDF]
• May 04, 2018, 13:15-14:00: Michelle Sweering
  S Felsner and G. Rote, On Primal-Dual Circle Representations, To appear in Proceedings of EuroCG, 2018. [PDF]
• May 04, 2018, 14:30-15:15: Simon Meinhard
  D. Gonçalves, L. Isenmann, C. Pennarun, Planar Graphs as L-intersection or L-contact graphs, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2018. [DOI]
• May 25, 2018, 13:15-14:00: Giovanni Campagnoni
  D. Larman, J. Matoušek, J. Pach and J. Töröcsik, A Ramsey-Type Result for Convex Sets, Bulletin of the London Mathematical Society, 26.2: 132-136, 1994. [DOI]
• May 25, 2018, 14:30-15:15: Daniel Bertschinger
  S.J. Kim, A Kostochka, and K Nakprasit, On the chromatic number of intersection graphs of convex sets in the plane, The electronic journal of combinatorics, 11.1: 52, 2004 [DOI]

All talks in CAB G15.2.

Topic and Papers

The title of the seminar is Intersections: Models, Representations & Algorithms.

Intersection graphs are defined on a collection of geometric objects that represents the set of vertices. There is an edge between two vertices if their corresponding geometric objects intersect. These graphs appear naturally in many combinatorial and computational problems. Depending on the class of geometric objects used to define them (segmens, circles, convex objects, curves), the induced intersection graph can have quite interesting and particular properties. What is their chromatic number, the size of their largest clique, or the size of their maximum independendt set? Another line of research is to ask which graphs are intersection graphs, and for which geometric objects can we recognize these graphs? What is the complexity of the objects needed to represent these graphs?

• S Felsner and G. Rote, On Primal-Dual Circle Representations, To appear in Proceedings of EuroCG, 2018. [PDF]
• S. Cabello, M. Jejčič, Refining the Hierarchies of Classes of Geometric Intersection Graphs, Electronic Notes in Discrete Mathematics, Volume 54, October, Pages 223-228, 2016 [DOI]
• J. L. Álvarez Rebollar, J. Cravioto Lagos and J. Urrutia, Crossing families and self crossing Hamiltonian cycles, In Proceedings of EGC, 2015. [PDF]
• S. Felsner, Rectangle and Square Representations of Planar Graphs, Thirty Essays on Geometric Graph Theory. Springer, New York, NY,, 213-248, 2013. [DOI]
• M.J. Alam, T. Biedl, S. Felsner, Linear-Time Algorithms for Hole-free Rectilinear Proportional Contact Graph Representations, Algorithmica, 67: 3-22, 2013. [DOI]
• P.K. Agarwal, N.H Mustafa, Independent Set of Intersection Graphs of Convex Objects in 2D, Computational Geometry, 34.2: 83-95, 2006 [DOI]
• J. Kratochvíl, J. Matoušek, String graphs requiring exponential representations, Journal of Combinatorial Theory, Series B, 1;53(1):1-4, 1991 [DOI]
• A. Pawlik et al., Triangle-Free Geometric Intersection Graphs with Large Chromatic Number, Discrete and Computational Geometry , Volume 50, Issue 3, pp 714–726, 2013. [DOI]
• A. Kostochka and J. Kratochvíl, Covering and coloring polygon-circle graphs, Discrete Mathematics, Volume 163, Issues 1–3, 1997. [DOI]
• B. Aronov, P. Erdös, W. Goddard, D. J. Kleitman, M. Klugerman, J. Pach and L. J. Schulman, Crossing families, Algorithms and Combinatorics, vol 14. Springer, Berlin, Heidelberg, 1997. [DOI]
• P. Valtr, On Mutually Avoiding Sets, Combinatorica, 14: 127-134, 1994. [DOI]
• D. Larman, J. Matoušek, J. Pach and J. Töröcsik, A Ramsey-Type Result for Convex Sets, Bulletin of the London Mathematical Society, 26.2: 132-136, 1994. [DOI]
• S.J. Kim, A Kostochka, and K Nakprasit, On the chromatic number of intersection graphs of convex sets in the plane, The electronic journal of combinatorics, 11.1: 52, 2004 [DOI]
• D. Gonçalves, L. Isenmann, C. Pennarun, Planar Graphs as L-intersection or L-contact graphs, Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 2018. [DOI]

Conditions

The seminar is held in English. Each talk is 45min. plus about 15min. discussion.
Every participant is expected to read, understand, and elaborate on a selected research paper. To this end, (s)he should give a 45-min. presentation about the paper. The process includes

1. getting an overview of the related literature;
2. understanding and working out the background/motivation: why and where are the questions addressed relevant?
3. understanding the contents of the paper in all details;
4. selecting parts suitable for the presentation;
5. presenting the selected parts in such a way that an audience with some basic background in geometry and graph theory can easily understand and appreciate it.

For more details, please refer to our guidelines for seminar talks. A number of additional related documents from different authors (both in English and German) are linked to from here.

A successful participation in the seminar requires the following:

1. a rehearsal talk, to be given in front of your supervisor at least one week prior to the plenary talk;
2. a satisfactory plenary talk;
3. attendance at all other talks.

---

Last modified: Tue Feb 13 18:42:43 CET 2018 by Michael Hoffmann.