The weak graph distance is a distance measure for embedded and immersed graphs which is motivated by its application to geographic networks. However, so far its computational complexity has only been partially understood, which is what we address in this paper. First, we extend previous NP-hardness results for deciding the directed version of this distance, showing that it remains NP-hard in various restricted settings as well as hardness of approximation. Then we present algorithmic results for deciding the weak graph distance in polynomial time under regularity conditions when \(G_1\) is immersed and \(G_2\) is planar embedded. Furthermore, we show two different FPT approaches for the case where both graphs are immersed in \(\mathbb {R}^2\) , parameterized in two ways of bounding the number of candidate solutions.