Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed
According to this abstract, deciding whether a 4-regular planar graph has a Hamiltonian Path is NP-complete.

Edited to add: Call a path that is allowed to revisit nodes a walk. Let $G$ be a graph on $n$ vertices and let us impose a weight of 1 on each edge. Then, $G$ has a Hamiltonian path if and only if the minimum weight walk in G visiting each vertex has weight $n-1$. In other words, if you can compute the minimum weight of a Hamiltonian walk, you can can detect the existence of Hamiltonian paths.