Geometry Seminar

---

Robust Algorithms for Unit Disk and Transmission Graphs

Speaker: Wolfgang Mulzer, FU Berlin

Location: Online Zoom-only

Videoconference link: https://youtu.be/Bzbl8klcNg4

Date: Tuesday, December 3, 2024, 2 p.m.

Synopsis:

We describe optimal robust algorithms for finding a triangle and the unweighted girth in a unit disk graph, as well as finding a triangle in a transmission graph. In the robust setting, the input is not given as a set of sites in the plane, but rather as an abstract graph. The input may or may not be realizable as a unit disk graph or a transmission graph.  If the graph is realizable, the algorithm is guaranteed to give the correct answer. If not, the algorithm will either give a correct answer or correctly state that the input is not of the required type.
 

Notes:

Contact Boris Aronov to be placed on the mailing list with notifications and Zoom seminar info.