Situational awareness during any disaster depends on effective communication and location tracking. In the case of underground mines, where the communication methods are mostly central, the whole communication channel would be rendered unusable during a disaster. To this end, we propose the use of Delay Tolerant Networks (DTN) to allow the miners to function in a distributed manner and help in locating the injured miners and routing distress messages. Due to the unavailability of GPS signals, the pillar numbers are used to identify the locations of the miners. For spatio-temporal routing of messages, we formulate a new scheme using Contact Graph Routing (CGR) and GAE-LSTM. CGR forms routes based on the future contact (meeting times) of DTN devices, assumed to be known, which might not be the case in underground mines. Thus, we use GAE-LSTM, a graph-based deep learning model, which predicts the location of miners with time, based on the previous movement information, i.e. speed, time, angle, and location (in terms of pillar numbers) of the DTN nodes. The DTN nodes then search's for other DTN nodes which will be at the same locations at same times. Using this information, a contact plan is formed which is used by the CGR for forming a route to send the messages.