Monday, April 16 at 3:00 PM
In the talk I would like to introduce a distance measures for comparing embedded graphs G1, G2, based on the Fréchet distance (work of M.Buchin, S.Sijben, C.Wenk). These distances use both the combinatorial structure and the embeddings of the graphs. For general embedded graphs, deciding this distance is NP-complete, but the authors gave an efficient algorithm for the case where the graphs is a tree. It remained open if there is an efficient algorithm for planar graphs. I will present a n^(2log^2(F)) time algorithm for the case of planar graphs, where n is the number of vertices of G2 and F is the number of faces of G1 and to talk about ideas for polynomial-time algorithms.
Download presentation (password protected)