This paper is the second part of the author's contribution on the topic of Safe Navigation for Indoor Mobile Robots. It presents a new solution to the exploration, self localization and map building problem taking advantage of the sensor-based navigation framework presented in the paper: Safe Navigation for Indoor Mobile Robots - Part I: A Sensor-based Navigation Framework. The model of the indoor environment is structured as an hybrid representation, both topological and geometrical, which is incrementally built during the exploration task. The topological aspect of the model captures the connectivity and accessibility of the different places in the environment, and the geometrical model holds up an accurate robot localization and map building method. To overpass the problem of drift inherited to the odometry when the robot navigates in large scale environments, a new dead-reckoning method is proposed combining laser readings and feedback control inputs. Embedding the self-localization and map building problem in a sensor-based navigation framework improves both the quality and the robustness of the representation built during the exploration phase and authorizes a further use to achieve safe navigation tasks successfully. Experiments are shown which confirm the interests of the proposed methodology.