In this paper, we propose a geometric algorithm for a map matching problem. More specifically, we are given a planar graph, H, with a straight-line embedding in a plane, a directed polygonal curve, T, and a distance value $\varepsilon >0$. The task is to find a path, P, in H, and a parameterization of T, that minimize the sum of the length of walks on T and P whereby the distance between the entities moving along P and T is at most $\varepsilon$ε, at any time during the walks. It is allowed to walk forwards and backwards on T and edges of H. We propose an algorithm with $\mathcal {O}\left( mn \left( m+n\right) \log (mn)\right)$ time complexity and $\mathcal {O}\left( mn \left( m+n\right) \right)$ space complexity, where m (n, respectively) is the number of edges of H (of T, respectively). As we show, the algorithm can be generalized to work also for weighted non-planar graphs within the same time and space complexities.