Before revision:  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:  Furthermore , we prove that deciding the distances based on the Fr\'echet distance remains NP-hard for planar embedded graphs and show how our general algorithmic approach yields an exponential time algorithm and a polynomial time approximation algorithm for this case.