Geometry Seminar

---

Distance Measures for Geometric Graphs

Speaker: Maike Buchin, Ruhr-University Bochum

Location: Online

Date: Tuesday, March 4, 2025, 2 p.m.

Synopsis:

Geometric graphs occur in many contexts and applications. In these one is often interested in their similarity, for instance if the graphs are different representations of the same road network. To do so, we introduce and compare different distance measures for geometric graphs. The measures that we introduce are based on the (weak) Frechet distance, a well-known distance measure for curves and surfaces. Our distance measures for geometric graphs take both their combinatorial structure as well as their geometric embedding into account. We study the computational complexity of these measures. For this, we first present a general algorithmic approach. Then we show that although deciding these distances is NP-complete in general, our approach yields polynomial time algorithms in several cases, for instance if the graphs are trees, or for the weak graph distance if both graphs are geometrically embedded in a nice way. Furthermore, we develop parameterized algorithms for the strong graph distance.

Notes:

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