One of the crucial steps in image mosaicing is global alignment, which requires finding the best image registration parameters by employing nonlinear minimization methods over correspondences between overlapping image pairs for a dataset. Based on graph theory, we propose a simple but efficient method to reduce the number of overlapping image pairs without any noticeable effect on the final mosaic quality. This reduction significantly lowers the computational cost of the image mosaicing process. The proposed method can be applied in a topology estimation process to reduce the number of image matching attempts. The method has been validated through experiments on challenging underwater image sequences obtained during sea trials with different unmanned underwater vehicles.