We consider a set of static towers with communication capabilities, but not within range of each other due to distance and obstacles. The goal is to achieve connectivity among the towers through a set of robots positioned in a way to act as gateways among the towers. The autonomous mobile robots are initially randomly deployed without necessarily being within range of each other, nor of the static towers, and without any common global coordinates. As the robots move, they may come within range of other robots or towers and can share information. We discuss the challenges of such a multi-robot positioning task without the common referential. We contribute a representation for the connectivity information that allows for the robots to share connectivity information without the need to merge the individual maps that they acquire while they navigate the environment. We further present several heuristics to guide the robot motion to explore the environment in search of towers and other robots. The robots analyze their own accumulated map and communicated information from other robots, and can determine if a complete positioning exists to achieve the joint connectivity goal. We further introduce different exploration heuristics, illustrate our algorithm in simulation, and compare the efficiency of the proposed exploration heuristics. We show that our representation is sufficient for the robot team to achieve a connected configuration with the static towers, without the need for merging their individual maps.