The increasing use of Autonomous Underwater Vehicles (AUV) in industrial or scientific applications makes the vehicle localization one of the challenging questions to consider for the mission success. Graph-SLAM has emerged as a promising approach in land vehicles, however, due to the complexity of the aquatic media, these systems have been rarely applied in underwater vehicles. The few existing approaches are focused on very particular applications and require important
amounts of computational resources, since they optimize the coordinates of the external landmarks and the vehicle trajectory, all together.This paper presents a simplified and fast general approach for stereo graph-SLAM, which optimizes the vehicle trajectory, treating the features out of the graph. Experiments with robots in aquatic environments show how the localization approach is effective underwater, online at 10fps, and with very limited errors. The implementation has been uploaded to a public repository, being available for the whole scientific community.