03.03.2026 16:00 Sariel Har-Peled:
On geometric intersection graphsMI 02.06.011 (Boltzmannstr. 3, 85748 Garching)
Many efficient algorithms have been developed over the years for planar graphs and more general graphs such as low genus graphs. Intersection graphs of geometric objects (in low dimensions) with some additional properties, such as fatness or low density, provide yet another family of graphs for which one can design better algorithms. This family is a vast extension of planar graphs, and yet is still algorithmically tractable for many problems. In this talk, we will survey this class of graphs, and some algorithms and intractability results known for such graphs, and outline open problems for further research.