Before revision:  Although we show that deciding the distances is NP-complete for general embedded graphs, we prove that our approach yields polynomial time algorithms for the distances based on the Fr\'echet distance if the graphs are trees, and for the distances based on the weak Fr\'echet distance if the graphs are trees or if they are plane. Furthermore , we prove that deciding the distances based on the Fr\'echet remains NP-complete for plane graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case.
After revision:  Although we show that deciding the distances is NP-complete for general embedded graphs, we prove that our approach yields polynomial time algorithms for the distances based on the Fr\'echet distance if the graphs are trees, and for the distances based on the weak Fr\'echet distance if the graphs are planar embedded. Moreover , we prove that deciding the distances based on the Fr\'echet remains NP-complete for plane graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case.