[Facets-of-complexity] Invitation to Monday's Lecture & Colloquium May 16.

["I.Brunke" <i.brunke@fu-berlin.de>]

Dear all,

our next Monday's Lecture and Colloquium will take place on May 16, back in attendance, at 14:15 & 16:00 at TU Berlin. There will also be a Zoom link for those who can not make it in person.

Invitation link for Zoom meeting:
https://tu-berlin.zoom.us/j/69716124232?pwd=dzFlcTFHMmFXRTE5QmZLaEV5N0FRUT09
No password is required.

You all are cordially invited.

Location:

Room MA 041 - Ground Floor
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Time: Monday, May 16 - 14:15

Lecture: Torsten Ueckerdt (Karlsruher Institut für Technologie, KIT)

Title: Stack and Queue Layouts of Planar Graphs

Abstract:

A colored linear layout of a graph is a total ordering of its vertices together with a partition of its edges into color classes. In a stack layout each color class is crossing-free, in a queue layout each color class is nesting-free, while in both cases our goal is to minimize the number of colors. In this talk we discuss on a higher level approaches to find good stack or queue layouts for planar graphs, including some recent breakthroughs and open problems.

Coffee & Tea Break :

Room MA 316 - Third Floor


Time: Monday, May 16 - 16:00 s.t.

Colloquium: Sandro Roch (Technische Universität Berlin)

Title: Arrangements of Pseudocircles: On Digons and Triangles

Abstract:

A pseudocircle is a simple closed curve in the plane. An intersecting arrangement of pseudocircles is a finite collection of pseudocircles so that any two intersect in exactly two points where they cross. Grünbaum conjectured in the 1970's that in the case of simple arrangements there are at most 2n - 2 digon cells, i.e. cells which have exactly two crossings on its boundary. I will present a result by Agarwal et al. (2004) which proves this conjecture for the special case of cylindrical arrangements. Based on that we show that the conjecture also holds whenever the arrangement contains three pseudocircles which pairwise form a digon cell. Moreover, I will present a result concerning the number of triangles in digon free arrangements, which disproves another conjecture by Grünbaum.
(Joint with S.Felsner and M.Scheucher)

Virenfrei. www.avast.com