Depth map images are an essential source of information for various applications such as robotics, autonomous vehicles, 3D cinema post-production, video games, and many others. These maps can be acquired by sensors such as LiDAR or time-of-flight cameras. However, the acquired data present large areas without information (or holes) or data with low-confidence values. Filling in these holes is crucial for robotics and other applications, which helps robots avoid obstacles or plan paths. In order to complete the depth data, we use a method that involves solving the variation of the infinity Laplacian guided by a color reference image of the considered scene. We associate the image grid to a graph and given the rectangular image domain \(\varOmega \subset \mathbb {R}^2\) , and a metric \(d_\textbf{xy}\) we created a manifold \(\mathcal {M}=(\varOmega , d_{\textbf{xy}}\) ), where we solve the infinity Laplacian. Our GPU implementation significantly reduces processing time. The contribution of this work is three-fold: i) we use a graph-based approach, ii) we used suitable graph metrics, and ii) we used a variation of the infinity Laplacian. Our results show that our proposal outperforms other contemporary models and performs similarly to approaches based on infinity Laplacian. Our implementation is fast and easy to implement and represents a low-cost tool for many applications. Future work will explore using different metrics and a more contemporary interpolation model.